백준 11048 이동하기 문제 : 세방향 이동 하지만 두방향만 체크

www.acmicpc.net/problem/11048

11048번: 이동하기

이동하기 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

18469

10689

7449

57.996%

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제 입력 1 복사

3 4 1 2 3 4 0 0 0 5 9 8 7 6

예제 출력 1 복사

31

#include <iostream>
#include <queue>
using namespace std;

int arr[1005][1005];
int keyy[3][2] = {{0, 1}, {1, 0}, {1, 1}};

struct Node {
	int y;
	int x;
	int candyn;
};

queue <Node> que;

int main(void)
{
	int n, m; // 1 ~ 1000
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cin >> arr[i][j];
	}
	if (n == 1 && m == 1)
	{
		cout << arr[n][m];
		return (1);
	}
	int maxsum = 0;
	Node node, temp;
	node.y = 1;
	node.x = 1;
	node.candyn = arr[1][1];
	que.push(node);
	while (!que.empty())
	{
		node = que.front();
		que.pop();
		for (int i = 0; i < 3; i++)
		{
			temp.y = node.y + keyy[i][0];
			temp.x = node.x + keyy[i][1];
			if (temp.y <= n && temp.x <= m)
			{
				//cout << temp.y << temp.x << temp.candyn<< "a\n";
				temp.candyn = node.candyn + arr[temp.y][temp.x];
				que.push(temp);
			}

		}
		if (maxsum < temp.candyn)
			maxsum = temp.candyn;
	}
	cout << maxsum;
	return (1);
}

 

처음 풀었던 방식 

하지만 메모리 초과가 일어난다. 

 

찾아보니 

www.acmicpc.net/board/view/4160

글 읽기 - 이동하기 문제 메모리 초과

메모리 초과 질문 있음 

Queue에 같은 좌표가 여러번 누적되면서 queue가 너무 커지면서 생기는 문제... 

따라서 예제로 준 문제는 잘 통과하지만 놉 

 

#include <iostream>
using namespace std;

int arr[1005][1005];

int main(void)
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cin >> arr[i][j];
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (i == 1 && j == 1)
				continue ;
			else if (i == 1 && j != 1)
				arr[i][j] += arr[i][j - 1];
			else if (i != 1 && j == 1)
				arr[i][j] += arr[i - 1][j];
			else
				arr[i][j] += max(arr[i][j - 1], arr[i - 1][j]);
		}
	}
	cout << arr[n][m];
	return (0);
}

 

다른 코드 참고해서 푼 문제 

기존 배열에서 가장 위 가장 왼쪽은 한방향에서만 오므로 += 로 처리해주고 

그보다 안쪽인 애들은 위나 왼쪽을 비교해서 더 큰수를 더하는 방식으로 처리해준다. 

그렇게 되면 가장 위부터 쭈루룩 확인할 수 있다. 

 

이 문제에서는 캔디를 주우러 목적지를 향해서만 갈 수 있기 때문에 (뒤로 갈 수 없음)

이런 풀이도 가능한 것 

visited배열 없어도 된다.