[백준] 16174번 : 점프왕 쩰리 (Large)

🔗 문제 링크

https://www.acmicpc.net/problem/16174

✍️ 문제 풀이

해당 문제는 점프왕 쩰리(Small)에서 이미 다룬 풀이이다. [풀이 링크]
똑같은 문제인데 다시 올리는 이유는 Small 문제에서 처리해주지 않은 어떤 부분이 Large 문제에서 오류를 발생시켜 수정했기 때문이다.

처리해주지 않은 부분은 바로 방문 처리였다. Small 문제에서는 방문 처리를 해주지 않았는데, 맵의 크기가 최대 3 x 3 크기였기 때문인지는 몰라도 오류 없이 통과 했었다. 그런데 Large 문제에서는 최대 64 x 64 크기이기 때문에 이 부분에서 오류가 발생한 것으로 보인다.

3
1 1 10
1 5 1
2 2 -1

위와 같은 예시에서 방문처리를 하지 않는다고 하면
1) (0, 0)에서 먼저 오른쪽, 아래쪽으로 이동하기 때문에 큐에는 (0, 1), (1, 0)이 삽입된다.
2) (0, 1)이 빠져나오면서 큐에 (0, 2), (1, 1)이 삽입된다.
3) 이후에는 (1, 0)이 빠져나오면서 (1, 1), (2, 0)이 삽입되어야 하는데, 여기서 (1, 1)이 중복으로 삽입되는 경우가 발생한다.

때문에 이러한 중복 방문을 방지하기 위해서 방문 처리를 해주어야 한다.

🖥️ 풀이 코드

#include <bits/stdc++.h>

using namespace std;
int visited[65][65];	// 방문 처리하는 visited 배열 추가

void BFS(int n, vector<tuple<int, int, int>> arr)
{
	queue<tuple<int, int, int>> q;
	q.push(arr[0]);		// 가장 첫 칸에 대한 데이터 큐에 삽입

	while (!q.empty())
	{
		// 최전방 노드에 저장된 데이터들을 변수로 저장 후 큐에서 삭제
		int y = get<0>(q.front());	// y좌표
		int x = get<1>(q.front());	// x좌표
		int value = get<2>(q.front());	// 칸의 값
		q.pop();

		// 칸의 값이 0이면 더 이상 이동 불가능 (문제 잘 읽을 것!)
		if (value == 0)
		{
			cout << "Hing";
			return;
		}

		// 오른쪽으로 이동하는 경우 : (현재 x 좌표 + 칸의 값 < n) && !visited[y][x + 칸의 값]일 때 이동 가능.)
		if (x + value < n && !visited[y][x + value])
		{
			q.push(arr[y * n + x + value]);		// arr 벡터에 접근할 때는 y 좌표에 n을 곱해주어야 함. -> (1, 0) 좌표의 칸은 arr[3]에 저장
			visited[y][x + value] = true;		// 이동한 칸에 대한 방문 처리
			if (get<2>(arr[y * n + x + value]) == -1)	// 목표 칸에 도착하면 HaruHaru 출력
			{
				cout << "HaruHaru";
				return;
			}
		}

		// 아래로 이동하는 경우 : (현재 y 좌표 + 칸의 값 < n) && !visited[y + 칸의 값][x]일 때 이동 가능
		if (y + value < n && !visited[y + value][x])
		{
			q.push(arr[(y + value) * n + x]);
			visited[y + value][x];
			if (get<2>(arr[(y + value) * n + x]) == -1)
			{
				cout << "HaruHaru";
				return;
			}
		}
	}
	cout << "Hing";		// 큐가 비워질 때까지 도착 못하면 도착 지점 도달 불가능
}

int main()
{
	int n;
	cin >> n;
	cin.ignore();

	vector<tuple<int, int, int>> arr(n * n);	// 각 칸에 대해 (y좌표, x좌표, 칸의 값) 저장 (arr[0] = (0, 0), arr[1] = (0, 1), ... , arr[3] = (1, 0), arr[4] = (1, 1), ... 과 같은 순서)

	// 맵 입력하기
	for (int i = 0; i < n; i++)
	{
		string input;
		getline(cin, input);

		istringstream ss(input);
		string stringBuffer;

		int j = 0;
		while (getline(ss, stringBuffer, ' '))
		{
			arr[i * n + j] = tuple<int, int, int>(i, j, stoi(stringBuffer));
			j++;
		}
	}

	BFS(n, arr);
}