BFS를 할 때에는 큐에 넣을 때 방문 표시를 해야 합니다.

제목대로, 또는 큐에서 뺀 뒤에 '이미 방문한 정점인지'를 체크해야 합니다.

 

그러지 않으면 트리가 아닌 이상 대부분의 경우 시간 초과나 메모리 초과를 받게 됩니다. 그 이유는 다음과 같은 예시에서 확인해볼 수 있습니다.

 

미로 탐색 문제에 대해, 동일한 로직의 아래 C++과 Python 3 코드를 봅시다.

 

[C++]

#include <bits/stdc++.h>
using namespace std;

string arr[105];
bool vis[105][105];

int dy[]{ 1, 0, -1, 0 };
int dx[]{ 0, 1, 0, -1 };

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	queue<pair<int, int>> q;
	q.push({ 0, 0 });

	int ans = 1;
	while (q.size())
	{
		for (int sz = q.size(); sz > 0; sz--)
		{
			pair<int, int> cur = q.front();
			q.pop();
			int y = cur.first;
			int x = cur.second;
			vis[y][x] = true;
			
			if (y == n - 1 && x == m - 1)
				return cout << ans << '\n', 0;

			for (int i = 0; i < 4; i++)
			{
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny >= 0 && ny < n && nx >= 0 && nx < m && arr[ny][nx] == '1' && !vis[ny][nx])
					q.push({ ny, nx });
			}
		}
		ans++;
	}
}

 

[Python]

from collections import deque
import sys

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

n, m = map(int, input().split())
arr = [input() for i in range(n)]
vis = [[False] * m for i in range(n)]

q = deque()
q.append((0, 0))

ans = 1

while q:
    for sz in range(len(q)):
        y, x = q.popleft()
        vis[y][x] = True

        if y == n - 1 and x == m - 1:
            print(ans)
            sys.exit(0)

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < m and arr[ny][nx] == '1' and not vis[ny][nx]:
                q.append((ny, nx))
    ans += 1

 

이 코드를 제출해 보면 각각 시간 초과나 메모리 초과를 받습니다. 어디가 문제가 되는 걸까요?

 

문제는 큐에 원소를 삽입하는 부분에 있습니다. 이 코드들은 큐에 원소를 삽입할 때 그저 삽입만 할 뿐, 삽입했다는 흔적을 어디에도 남기지 않습니다. 대신에 큐에서 뺀 뒤에 vis 배열에 표시를 해주고 있는데, 왜 이걸로는 충분하지 않을까요?

 

다음의 상황을 생각해 봅시다. 모든 칸이 갈 수 있는 칸일 때, 왼쪽 위에서 탐색을 시작하여 해당 칸이 큐에 들어간 횟수를 나타내어 보면, 첫 칸이 큐에서 나온 후의 모습은 다음과 같습니다. vis 배열의 상태는 false를 파랑으로, true를 빨강으로 표시했습니다.

 

그 다음에는 이 칸에서 갈 수 있는 아래 칸, 오른쪽 칸이 각각 큐에 들어가게 됩니다. 위 코드에서는 아래 칸을 먼저 큐에 넣으니 큐에서 나오는 것도 아래 칸이 먼저입니다.

 

마찬가지로 오른쪽 칸과 아래 칸 모두 vis 표시가 안 되어있으니 큐에 넣습니다. 그 다음 큐에서 나올 칸은 가장 윗 줄의 두 번째 칸입니다.

 

그런데 여기서 이제 이상한 점이 있습니다. 분명 두 번째 줄의 두 번째 칸은 이미 큐에 넣은 적이 있는데, 아직까지 방문 표시가 안 되어있네요? vis가 false니까, 이 좌표는 다시 한 번 큐에 들어가게 됩니다.

 

다음은 아랫줄 두 번째 칸이 큐에 들어갑니다.

 

이제 가운데 칸이 큐에서 나왔습니다. 그런데 이번에도 아까와 마찬가지로 아래의 칸은 이미 큐에 들어가 있지만 vis에는 표시가 안 되어있네요. 그러므로 아랫칸, 오른쪽 칸이 모두 큐에 또 들어갑니다. 그리고 그 다음에 큐에서 나올 칸은... 또 가운데 칸입니다.

 

방금 전과 똑같은 상황입니다. 아랫쪽 칸은 이미 큐에 두 번 들어갔고, 오른쪽 칸도 이미 큐에 한 번 들어갔지만, vis 표시가 안 되어있으니 둘 다 또 큐에 넣습니다.

 

이번에도 아래 칸이 큐에 두 번이나 들어갔지만 vis는 여전히 false이므로 또 큐에 넣습니다. 그러면 이제 다음과 같은 상태가 됩니다.

 

아랫줄 두 번째 칸과 두 번째 줄 오른쪽 칸 모두 큐에서 세 번 빠져나오는 동안 오른쪽 아래 칸은 한 번도 vis에 체크된 적이 없습니다. 이리하여 오른쪽 아래 칸은 큐에 6번 들어가게 되고, 최종적으로는 아래와 같은 형태가 됩니다.

 

자, 어떻습니까? 모든 칸을 한 번씩만 방문해야 할 BFS가, 겨우 3x3 크기의 격자에서 무려 6번이나 방문을 당하는 칸이 생기는 경우를 발생시키고 말았습니다. 이런 현상이 생긴 이유는 바로 하나의 칸을 여러 칸에서 동시에 방문을 하려고 할 수 있는데 이를 방지하지 못했기 때문입니다.

 

3x3 칸에서는 6번으로 끝나지만, 만일 20x20짜리 칸에 이와 같은 문제가 벌어지면 각 칸에 대한 방문 횟수는 다음과 같아집니다.

 

세상의 그 어떤 빠른 컴퓨터도 싱글코어로 1초 안에 각 칸을 저만큼 방문할 수는 없습니다. 게다가 문제의 최대 제한인 100x100칸에 이와 같은 일이 벌어진다면, 우주가 탄생했을 때부터 지금까지 프로그램을 계속 돌렸더라도 아직 모든 칸을 방문하지 못했을 것입니다.

 

만일 큐에 넣는 순간 바로 해당 칸에 vis를 체크해두었더라면, 이후에는 다른 칸이 해당 칸을 다시 방문하려고 해도 이미 vis에 true 표시가 되어있기 때문에 다시 큐에 넣지 않을 것이고, 따라서 중복 방문이 발생하지 않습니다.

 

적절하게 고쳐서 정답을 받는 코드들은 다음과 같습니다.

 

[C++]

#include <bits/stdc++.h>
using namespace std;

string arr[105];
bool vis[105][105];

int dy[]{ 1, 0, -1, 0 };
int dx[]{ 0, 1, 0, -1 };

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	queue<pair<int, int>> q;
	q.push({ 0, 0 });
	vis[0][0] = true;

	int ans = 1;
	while (q.size())
	{
		for (int sz = q.size(); sz > 0; sz--)
		{
			pair<int, int> cur = q.front();
			q.pop();
			int y = cur.first;
			int x = cur.second;
			
			if (y == n - 1 && x == m - 1)
				return cout << ans << '\n', 0;

			for (int i = 0; i < 4; i++)
			{
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny >= 0 && ny < n && nx >= 0 && nx < m && arr[ny][nx] == '1' && !vis[ny][nx])
				{
					q.push({ ny, nx });
					vis[ny][nx] = true;
				}
			}
		}
		ans++;
	}
}

 

[Python]

from collections import deque
import sys

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

n, m = map(int, input().split())
arr = [input() for i in range(n)]
vis = [[False] * m for i in range(n)]

q = deque()
q.append((0, 0))
vis[0][0] = True

ans = 1

while q:
    for sz in range(len(q)):
        y, x = q.popleft()

        if y == n - 1 and x == m - 1:
            print(ans)
            sys.exit(0)

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < m and arr[ny][nx] == '1' and not vis[ny][nx]:
                q.append((ny, nx))
                vis[ny][nx] = True
    ans += 1

 

큐에 넣을 때 표시하는 대신, 큐에서 뺀 뒤에 현재 칸이 이미 방문되었는지를 확인해서 이미 방문했을 경우 건너뛰는 방법도 있습니다. 이 경우 큐에 중복 원소가 들어가기는 하지만, 딱 한 번만 처리하기 때문에 중복이 또 다른 중복을 낳는 결과는 피할 수 있습니다. 실제로 이 경우 모든 정점에 대해 큐에 들어가는 총 횟수는 간선의 개수만큼으로 제한되기 때문에 시간 복잡도상 문제가 발생하지 않으며, 다익스트라 알고리즘의 경우 이와 같은 방법을 통해 중복 방문을 해결하는 것이 일반적입니다.