[Algorithm] BFS (다차원 배열)

https://blog.encrypted.gg/941

[실전 알고리즘] 0x09강 - BFS

대부분의 내용을 위의 게시물을 참고해 작성한 글이다.

---

BFS의 기본 개념

BFS를 사용하면 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문할 수 있다. BFS는 원래 그래프에서 모든 노드를 방문할 때 사용하는 것이 맞지만... 그냥 다차원 배열에서도 사용할 수 있다고 생각하자. (다차원 배열에서의 탐색이 필요한 문제는 전부 BFS로 푼다고 생각해도 된다. DFS는 그래프나 트리에서 자주 사용됨)

 

BFS에는 큐가 사용된다. 동작 순서를 정리하면 다음과 같다.

1. 시작점을 큐에 집어넣은 후 방문 처리를 한다. (여기까지가 초기 세팅)
2. 큐의 앞에서 값을 꺼낸 후, 그 칸에 인접한 칸들을 검사한다. (여기에서는 상하좌우 네 칸만 생각)
3. 이미 방문한 점이면 무시하고, 방문하지 않았다면 방문 처리를 한 후 큐에 집어넣는다.
4. 큐가 빌 때까지 2~3 과정을 반복한다.

이렇게 하면 시작점과 연결된 모든 칸들을 방문할 수 있다. (이는 후술할 Flood Fill에서 자세하게 설명한다.)

모든 칸이 큐에 한 번씩 들어갔다 나오므로 N개의 칸이 있다고 한다면 BFS를 한 번 시행할 때의 시간 복잡도는 O(N)이다.

행이 R개이고 열이 C개면 O(RC)가 된다.

 

BFS를 구현할 때 많이 실수하는 부분은 다음과 같다

• 시작점 방문 표시 & 큐에 추가를 하지 않음 (초기 세팅 X)
  • 시작점을 두 번 방문할 수 있기 때문에 초기 세팅을 해줘야 함
• 방문 표시를 큐에 넣을 때가 아니라 뺄 때 함
  • 큐에서 원소를 뺄 때 방문 표시를 한다면, 이미 앞서 큐에 원소를 집어넣은 상태이므로 같은 원소가 큐에 여러 번 들어가 문제를 일으킬 수 있음
• 이웃한 원소 범위 체크를 잘못함

pair

두 자료형을 묶어서 편리하게 저장할 수 있게 하는 클래스이다. (utility 헤더에 있음. 다만 algorithm 헤더에 포함됨)

make_pair 메소드로 편리하게 pair 객체를 만들 수 있다.

C++11부터는 중괄호로도 쉽게 만들 수 있다.

각각의 값은 first와 second로 접근할 수 있다.

그리고 연산자 오버로딩이 되어있어 비교 연산자를 바로 사용할 수 있다.

 

2차원 배열에서의 좌표를 pair에 저장하면 BFS의 큐에 손쉽게 넣고 뺄 수 있다.

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

int main() {
    pair<int, int> p1 = make_pair(1, 2);
    pair<int, int> p2 = {3, 4}; // C++11부터 지원
    cout << p1.first << " " << p1.second << endl;
    if (t2 < t1) cout << 1; // 비교 연산자 사용
}

 

BFS 활용 1 - Flood Fill (플러드 필)

앞서 말하자면 플러드 필 알고리즘은 DFS로도 구현이 가능하다. 여기에서는 BFS에서의 플러드 필만 설명한다.

 

플러드 필은 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 그림 프로그램의 채우기 도구에 사용된다. 이를 시각화한 좋은 자료가 있어서 가져와 봤다.

35초부터 보면 된다. 시작점을 중심으로 퍼져나가는 것을 볼 수 있다.

이제 이를 활용한 백준 문제를 풀어보자. (https://www.acmicpc.net/problem/1926)

어떤 큰 도화지에 그림이 있는데, 그림 개수와 그 중 가장 큰 그림의 넓이를 구해야 한다. 이때, 1로 연결된 것들이 그림이고, 그림에 포함된 1의 개수가 그림의 넓이라고 한다. 그럼 이 문제를 이렇게 생각할 수 있다.

• 1로 연결된 것들이 그림
  • 어떤 특정점에서 값이 1인 모든 연결된 점들을 찾아야 함
• 그림에 포함된 1의 개수가 그림의 넓이
  • 각 그림에 있는 연결된 모든 점들을 이동할 때마다 개수를 셈

연결된 모든 점들을 방문해야 하므로 플러드 필 알고리즘을 사용하면 된다.

// 도화지에 있는 그림의 개수 -> BFS의 실행 횟수
// 가장 큰 그림의 넓이 -> 각 BFS마다 큐에 들어갔다 나가는 좌표의 개수 중 최대값

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

int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
int n, m;
int paint[501][501]; // 0번 인덱스 사용 X
int cnt = 0; // 그림 개수
int paintSize = 1; // 해당 그림의 넓이
vector<int> paintSizes; // 모든 그림 넓이 저장
queue<pair<int, int>> q; // BFS에서 방문한 칸 저장할 큐

void BFS() {
	while (!q.empty()) {
		// 큐의 맨 앞에서 좌표 가져옴
		pair<int, int> currentPos = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			// 새로 이동할 좌표를 구함
			int newX = currentPos.first + dx[i];
			int newY = currentPos.second + dy[i];

			// 해당 좌표 범위 검사
			if (newX < 0 || newX > m || newY < 0 || newY > n) continue;

			if (paint[newY][newX]) {
				// 해당 좌표 이동 방문 처리하고 큐에 추가
				paint[newY][newX] = 0;
				paintSize++;
				q.push(make_pair(newX, newY));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> paint[i][j];
		}
	}

	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= m; x++) {
			paintSize = 1;

			if (paint[y][x]) { // 1인 경우
				cnt++; // 그림 개수 + 1
				paint[y][x] = 0; // 방문 처리
				q.push(make_pair(x, y)); // 현재 방문한 점 큐에 추가
				BFS();
				paintSizes.push_back(paintSize); // 해당 그림의 넓이 저장
			}
		}
	}

	cout << cnt << '\n';
	
	if (paintSizes.empty()) 
		cout << 0;
	else 
		cout << *max_element(paintSizes.begin(), paintSizes.end());
}

이 코드를 하나 하나씩 살펴보자.

cin >> n >> m;

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cin >> paint[i][j];
    }
}

for (int y = 1; y <= n; y++) {
    for (int x = 1; x <= m; x++) {
        paintSize = 1;

        if (paint[y][x]) { // 1인 경우
            cnt++; // 그림 개수 + 1
            paint[y][x] = 0; // 방문 처리
            q.push(make_pair(x, y)); // 현재 방문한 점 큐에 추가
            BFS();
            paintSizes.push_back(paintSize); // 해당 그림의 넓이 저장
        }
    }
}

먼저 도화지의 크기 n과 m을 입력받고, paint 배열에 그림의 위치를 입력받는다.

그런 다음 도화지 전체 칸에 대해 검사를 시작한다. paintSize는 각 그림마다의 크기를 임시로 저장한다. 배열을 왼쪽 위부터 오른쪽 아래까지 순서대로 이동하다가 그림이 그려진 부분 (paint[y][x]가 1인 부분)을 만나면 그림의 개수 cnt를 1 증가시킨 후, 그 칸을 BFS의 시작점으로 보고 초기 세팅 (방문 처리, 큐에 추가)를 해준다음 BFS 함수를 호출한다.

void BFS() {
	while (!q.empty()) {
		// 큐의 맨 앞에서 좌표 가져옴
		pair<int, int> currentPos = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			// 새로 이동할 좌표를 구함
			int newX = currentPos.first + dx[i];
			int newY = currentPos.second + dy[i];

			// 해당 좌표 범위 검사
			if (newX < 0 || newX > m || newY < 0 || newY > n) continue;

			if (paint[newY][newX]) {
				// 해당 좌표 이동 방문 처리하고 큐에 추가
				paint[newY][newX] = 0;
				paintSize++;
				q.push(make_pair(newX, newY));
			}
		}
	}
}

BFS는 큐에 방문할 칸이 있는 동안 계속 반복되기 때문에 먼저 큐가 비어있지 않은지 확인한다. 그런 후에 큐의 맨 앞에서 좌표를 가져와 currentPos에 저장한 후 상하좌우 네 방향에 대해 검사를 시작한다. 만약 인접한 칸을 방문할 수 있다면 (paint[newY][newX]가 1이면) 해당 좌표에 방문 처리를 한 후 큐에 집어넣는다. 이때, 해당 그림의 크기를 세야하기 때문에 paintSize를 1만큼 증가시킨다.

 

한 번 실행된 BFS가 끝나게 된다면 도화지에 있는 그림 중 하나의 그림에 대한 처리가 끝나게 된다. 이런 식으로 도화지에 있는 모든 그림에 대해 BFS를 실행하면 그림의 개수와 각 그림마다의 크기를 구할 수 있고, 그 중 크기가 가장 큰 그림을 골라 출력하면 된다.

BFS 활용 2 - 거리 측정 (최단 거리 찾기)

BFS를 활용해 다차원 배열에서 특정 위치까지의 최단 거리를 찾을 수 있다. 모든 칸을 방문하는 것은 BFS, DFS 둘 다 할 수 있지만 DFS는 어떤 칸과 그와 인접한 다른 칸까지의 거리가 1만큼 차이난다는 것을 보장할 수 없으므로 처음 발견되는 해답이 최단거리인 것을 보장할 수 없다. 반면 BFS는 인접한 노드부터 방문하기 때문에 경로 탐색 시 처음으로 찾는 해답이 최단거리인 것을 보장할 수 있다. 그러므로 거리 측정 (최단 거리 찾기)은 BFS만 가능하다.

 

거리를 계산하는 방법은 간단하다. 거리를 저장할 별도의 배열을 만든 후 (-1 등의 특정 값으로 초기화 하는 것을 잊지 말자!), 시작점을 0으로 두고, 인접한 칸으로 이동할 때마다 현재 칸의 거리 + 1을 해주면 시작점으로부터 인접한 그 칸까지의 거리를 구할 수 있다. 도착점까지 이 과정을 반복하면 도착점에 대한 거리 배열의 값은 시작점으로부터 도착점까지의 최단 거리가 된다.

0	1	2	3
1	2	*	4
2	3	*	5
3	4	5	6
4	5	6	7

위는 왼쪽 위부터 오른쪽 아래까지 BFS로 이동했을 때 거리 배열에 담긴 계산 결과이다. *는 이동할 수 없는 벽을 나타낸다. 앞서 설명했듯이 시작점의 거리를 0으로 두고, BFS를 실행하며 거리를 계산하면 도착점까지의 최단 거리가 7이라는 결과를 얻을 수 있다.

 

이를 활용한 백준 문제를 풀어보자. (https://www.acmicpc.net/problem/2178)

미로에서 이동할 수 있는 / 없는 칸 1과 0이 있고, (1, 1)에서 출발해 (N, M)까지 이동할 때 지나야하는 최단 칸 수를 구해야 한다. (N, M)은 미로의 제일 오른쪽 아래 칸이므로 왼쪽 위에서 오른쪽 아래까지 가는 최단 거리를 구하면 된다.

// 미로 최대 10,000칸 => O(N^2)까지 가능
// (1, 1) -> (N, M)까지 최단 거리 => 오른쪽 아래로 계속 움직이면 됨 => 오른쪽 -> 아래 -> 왼쪽 -> 위 순서로 검사
// 동시에 dist 배열에서 시작점에서부터 각 점까지의 거리를 저장 -> 마지막에 dist[n][m] + 1 출력 (출발점 포함)

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

int n, m;
int maze[101][101] = { 0, }; // 0번 인덱스 사용 X
int dist[101][101]; // 출발점부터의 거리를 계산할 배열
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
queue<pair<int, int>> q;

void BFS() {
	while (!q.empty()) {
		// 큐에서 꺼내기
		pair<int, int> currentPos = q.front(); q.pop();

		for (int i = 0; i < 4; i++) {
			// 새롭게 이동할 좌표 만들기
			int newX = currentPos.first + dx[i];
			int newY = currentPos.second + dy[i];

			if (newX < 0 || newX > m || newY < 0 || newY > n) continue; // 범위 벗어나는 지 확인

			if (maze[newY][newX] && dist[newY][newX] == -1) { // 이동할 수 있는 칸이고, 아직 거리를 계산하지 않았다면
				q.push(make_pair(newX, newY)); // 큐에 추가
				dist[newY][newX] = dist[currentPos.second][currentPos.first] + 1; // dist에 저장할 거리 계산. 인접한 점들까지의 거리 => 현재 위치까지의 거리 + 1
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int y = 1; y <= n; y++) {
		string inputLine; // 붙어서 입력으로 주어짐 -> 문자열로 받은 다음 하나씩 가져오기
		cin >> inputLine;
		for (int x = 1; x <= m; x++) maze[y][x] = int(inputLine.at(x - 1)) - 48; // 49: 1
	}
	for (int i = 0; i <= n; i++) fill(dist[i], dist[i] + m + 1, -1); // dist 배열 각 줄마다 -1로 채우기

	// 출발점 관련 초기값 설정
	q.push(make_pair(1, 1));
	maze[1][1] = 0;
	dist[1][1] = 0;
	BFS();

	cout << dist[n][m] + 1; // +1 -> 출발점 포함
}

자세하게 살펴보자.

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int y = 1; y <= n; y++) {
		string inputLine; // 붙어서 입력으로 주어짐 -> 문자열로 받은 다음 하나씩 가져오기
		cin >> inputLine;
		for (int x = 1; x <= m; x++) maze[y][x] = int(inputLine.at(x - 1)) - 48; // 49: 1
	}
	for (int i = 0; i <= n; i++) fill(dist[i], dist[i] + m + 1, -1); // dist 배열 각 줄마다 -1로 채우기

	// 출발점 관련 초기값 설정
	q.push(make_pair(1, 1));
	maze[1][1] = 0;
	dist[1][1] = 0;
	BFS();

	cout << dist[n][m] + 1; // +1 -> 출발점 포함
}

입력이 붙은 상태로 주어지므로 문자열로 받아야 하고, 각 문자열에 있는 각각의 문자를 정수로 변환해 maze 배열에 저장한다. 그리고 거리를 나타내는 dist 배열 전체를 -1로 초기화한다. 그러고 나서 시작점에 대한 초기화를 해준 후 BFS 함수를 호출한다.

void BFS() {
	while (!q.empty()) {
		// 큐에서 꺼내기
		pair<int, int> currentPos = q.front(); q.pop();

		for (int i = 0; i < 4; i++) {
			// 새롭게 이동할 좌표 만들기
			int newX = currentPos.first + dx[i];
			int newY = currentPos.second + dy[i];

			if (newX < 0 || newX > m || newY < 0 || newY > n) continue; // 범위 벗어나는 지 확인

			if (maze[newY][newX] && dist[newY][newX] == -1) { // 이동할 수 있는 칸이고, 아직 거리를 계산하지 않았다면
				q.push(make_pair(newX, newY)); // 큐에 추가
				dist[newY][newX] = dist[currentPos.second][currentPos.first] + 1; // dist에 저장할 거리 계산. 인접한 점들까지의 거리 => 현재 위치까지의 거리 + 1
			}
		}
	}
}

앞서 설명한 BFS의 동작 방식은 현재 예제 이후로 생략한다. 마지막으로 나오는 if문을 보면 새로운 좌표가 이동할 수 있는 곳 (maze[newY][newX]가 1)인지, 그리고 아직 거리를 계산하지 않은 곳 (dist[newY][newX]가 초기값인 -1)인지 확인한 후, 두 조건에 모두 부합한다면 그 좌표를 큐에 집어넣고, 거리를 계산한다.

BFS 활용 3 - 시작점이 여러 개인 BFS

지금까지 배운 내용을 토대로 생각하면, 시작점이 여러 개인 경우에도 단순히 전체 배열을 돌면서 시작점마다 BFS를 실행시키면 해결 될 것 같다. 물론 이것도 제대로 동작하긴 한다. 다만, 이전과 같은 방법으로 MxN 배열을 모두 돌면서 시작점이 나올 때마다 BFS를 실행시키게 된다면 각 BFS의 시간 복잡도가 O(MN)이고, 배열을 모두 도는 데도 O(MN)의 시간 복잡도가 필요하기 때문에 총 O(M^2 * N^2)의 시간 복잡도가 소요된다. 이는 매우 비효율적이다. 그럼 이 문제를 어떻게 개선할 수 있을까?

 

해결 방법은 의외로 간단하다. 모든 시작점을 미리 큐에 집어넣고 BFS를 실행하면 된다. 배열을 입력받을 때 시작점을 미리 파악한 후 BFS를 실행하면 O(MN) + O(MN)이 되어 최종 시간 복잡도는 O(MN)이 된다.

 

이를 활용한 백준 문제를 풀어보자. (https://www.acmicpc.net/problem/7576)

토마토가 저장된 상자가 있고, 이미 익은 토마토는 상하좌우로 인접한 익지 않는 토마토에 영향을 준다. 그리고 모든 토마토가 익는데 걸리는 최소 일수를 구해야 한다. 만약 모든 토마토가 익지 못하는 상황이라면 -1를 출력한다.

 

여기서 생각할 수 있는 것은 다음과 같다.

• 이미 익은 토마토가 주변 토마토에 영향을 주고, 익는 데 걸리는 시간을 구해야 함
  • 최단 거리를 구하는 BFS를 생각해낼 수 있음
• 익은 토마토가 한 개만 있다는 조건이 없음
  • 시작점이 여러 개인 BFS를 생각해낼 수 있음

최단 거리를 구하면서 시작 점이 여러 개인 BFS를 사용하면 된다.

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

int m, n;
int box[1001][1001]; // 0번 인덱스 사용 X
int dist[1001][1001];
queue<pair<int, int>> q; // (X, Y)
int dy[4] = { -1, 1, 0, 0 }; // 상하좌우 순서로 이동
int dx[4] = { 0, 0, -1, 1 };

void BFS() {
	while (!q.empty()) {
		auto currentPos = q.front(); q.pop(); // 큐 맨 앞에서 꺼내기

		for (int i = 0; i < 4; i++) { // 상하좌우에 있는 토마토에 대해 방문 준비
			int newX = currentPos.first + dx[i];
			int newY = currentPos.second + dy[i];

			if (newX <= 0 || newX > m || newY <= 0 || newY > n) continue; // 범위를 벗어나면
			if (box[newY][newX] == 1 || box[newY][newX] == -1) continue; // 새로운 좌표의 토마토가 이미 익었거나, 들어있지 않은 칸이면

			dist[newY][newX] = dist[currentPos.second][currentPos.first] + 1; // 그 토마토에 대해 일수 + 1
			box[newY][newX] = 1; // 익은 것으로 처리
			q.push(make_pair(newX, newY)); // 큐에 추가
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n; // 상자 크기 입력

	// 상자에 저장된 토마토 정보 입력
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> box[i][j];

			// 시작점의 위치를 미리 큐에 저장
			if (box[i][j] == 1) q.push(make_pair(j, i)); // (X, Y)
			else if (box[i][j] == 0) dist[i][j] = -1;
			else if (box[i][j] == -1) dist[i][j] = -2; // 빈 칸인 경우
		}
	}

	BFS();

	// 만약 익지 않은 토마토가 하나라도 있다면 -1을 출력 후 종료, 아니면 모두 익는데 걸린 최소 날짜(dist에서 가장 큰 수) 출력
	int result = -1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (box[i][j] == 0) {
				cout << -1;
				return 0;
			}
			else {
				if (dist[i][j] == -2) continue; // 빈 칸인 경우 스킵
				result = max(result, dist[i][j]);
			}
		}
	}

	cout << result;
}

// 상자에 저장된 토마토 정보 입력
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cin >> box[i][j];

        // 시작점의 위치를 미리 큐에 저장
        if (box[i][j] == 1) q.push(make_pair(j, i)); // (X, Y)
        else if (box[i][j] == 0) dist[i][j] = -1;
        else if (box[i][j] == -1) dist[i][j] = -2; // 빈 칸인 경우
    }
}

BFS();

// 만약 익지 않은 토마토가 하나라도 있다면 -1을 출력 후 종료, 아니면 모두 익는데 걸린 최소 날짜(dist에서 가장 큰 수) 출력
int result = -1;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (box[i][j] == 0) {
            cout << -1;
            return 0;
        }
        else {
            if (dist[i][j] == -2) continue; // 빈 칸인 경우 스킵
            result = max(result, dist[i][j]);
        }
    }
}

상자에 저장된 토마토의 정보를 입력하면서, 익은 토마토 (입력받은 값이 1)가 나오면 그 좌표를 큐에 저장한다. 익지 않은 토마토 (입력받은 값이 0)인 경우 거리 배열의 값을 -1로 설정하고, 이동할 수 없는 빈 칸 (입력받은 값이 -1)인 경우 거리 배열의 값을 -2로 설정한다. 입력이 모두 끝났으면 BFS를 실행하고, BFS가 끝나면 배열을 모두 돌면서 익지 않은 토마토가 있는 지 확인한다. 만약 모두 익었다면 거리 배열의 최대값을 출력한다.

void BFS() {
	while (!q.empty()) {
		auto currentPos = q.front(); q.pop(); // 큐 맨 앞에서 꺼내기

		for (int i = 0; i < 4; i++) { // 상하좌우에 있는 토마토에 대해 방문 준비
			int newX = currentPos.first + dx[i];
			int newY = currentPos.second + dy[i];

			if (newX <= 0 || newX > m || newY <= 0 || newY > n) continue; // 범위를 벗어나면
			if (box[newY][newX] == 1 || box[newY][newX] == -1) continue; // 새로운 좌표의 토마토가 이미 익었거나, 들어있지 않은 칸이면

			dist[newY][newX] = dist[currentPos.second][currentPos.first] + 1; // 그 토마토에 대해 일수 + 1
			box[newY][newX] = 1; // 익은 것으로 처리
			q.push(make_pair(newX, newY)); // 큐에 추가
		}
	}
}

이미 익은 토마토가 있거나, 빈 칸인 경우 이동하지 않고, 그 이외의 경우에는 익지 않은 토마토가 있는 것으로 판단해 일수 계산과 방문 처리를 한 후 좌표를 큐에 집어넣는다.

BFS 활용 4 - 시작점이 두 종류인 BFS

앞서 말하자면, 이후에 소개할 예제는 두 종류의 시작점 중 하나가 전혀 영향을 받지 않고 독립적인 경우에만 사용이 가능한 방식이다. 만약 두 종류의 BFS가 서로 영향을 준다면 백트래킹 기법을 사용해 문제를 해결해야 한다. 이 내용은 주제를 벗어나므로 서술하지 않겠다.

 

이전 활용이 같은 종류의 시작점이 여러 개인 경우였다면, 이번에는 시작점의 종류가 서로 다른 경우의 활용이다. (이 차이를 꼭 이해하자.) 이런 경우에는 독립적인 BFS를 먼저 실행한 후, 독립적이지 않은 BFS를 실행하면 된다. 이것만 보면 이해하기 어려우니 바로 예제를 살펴보자. (https://www.acmicpc.net/problem/4179) 여담이지만, 나도 이걸 처음 풀 때 매우 어려웠다. 거의 6시간동안 잡고 있었던 것 같은데 문제를 풀지 못했고, 결국 정답 코드를 참고했다.

 

문제를 통해 생각할 수 있는 것은 다음과 같다.

• 지훈이와 불이라는 서로 종류가 다른 것들이 각자의 위치에서 시작해 미로를 따라 이동함
  • 시작점이 두 종류인 BFS
• 불은 미로를 이동하는 데 아무런 영향을 받지 않지만, 지훈이는 불보다 먼저 지나가야 함
  • 두 종류의 BFS 중 하나가 독립적이고, 다른 하나는 영향을 받음
• 지훈이의 위치에서부터 각 미로의 가장자리에 접한 공간으로 불이 번지기 전에 탈출할 수 있는 지의 여부와 최소 시간을 구해야 함
  • 최단 거리 찾기 BFS

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

int R, C;
string maze[1000];
int jihunDist[1000][1000]; // 지훈이의 이동 거리 (시간으로 생각)
int fireDist[1000][1000]; // 불의 이동 거리 (시간으로 생각)
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> R >> C; // 행렬 크기 입력

	for (int i = 0; i < R; i++) { // dist 배열들 -1로 초기화	
		fill(jihunDist[i], jihunDist[i] + C, -1);
		fill(fireDist[i], fireDist[i] + C, -1);
	}

	for (int i = 0; i < R; i++)
		cin >> maze[i];

	queue<pair<int, int>> jihunQueue;
	queue<pair<int, int>> fireQueue;
	for (int i = 0; i < R; i++) { // 지훈, 불 시작 위치 찾기 & 초기화
		for (int j = 0; j < C; j++)
		{
			if (maze[i][j] == 'F') {
				fireQueue.push(make_pair(j, i)); // (x, y)
				fireDist[i][j] = 0;
			}
			if (maze[i][j] == 'J') {
				jihunQueue.push(make_pair(j, i)); // (x, y)
				jihunDist[i][j] = 0;
			}
		}
	}

	// 불 먼저 BFS
	while (!fireQueue.empty()) {
		auto currentPos = fireQueue.front(); fireQueue.pop(); // 큐의 앞에서 pop
		for (int i = 0; i < 4; i++) {
			int newX = currentPos.first + dx[i];
			int newY = currentPos.second + dy[i];

			if (newX < 0 || newX >= C || newY < 0 || newY >= R) continue; // 범위 체크
			if (fireDist[newY][newX] >= 0 || maze[newY][newX] == '#') continue; // 이미 방문한 곳 or 벽이면 체크

			fireDist[newY][newX] = fireDist[currentPos.second][currentPos.first] + 1; // 새로 이동할 위치에 대해 거리 + 1
			fireQueue.push(make_pair(newX, newY));
		}
	}

	// 지훈이 BFS
	while (!jihunQueue.empty()) {
		auto currentPos = jihunQueue.front(); jihunQueue.pop(); // 큐의 앞에서 pop
		for (int i = 0; i < 4; i++) {
			int newX = currentPos.first + dx[i];
			int newY = currentPos.second + dy[i];

			// 범위 벗어남 -> 탈출 성공
			// 큐에 거리순으로 들어가므로 탈출 성공한 곳 바로 출력
			if (newX < 0 || newX >= C || newY < 0 || newY >= R) {
				cout << jihunDist[currentPos.second][currentPos.first] + 1;
				return 0;
			}

			if (jihunDist[newY][newX] >= 0 || maze[newY][newX] == '#') continue; // 이미 방문 or 벽인 경우
			if (fireDist[newY][newX] != -1 && jihunDist[currentPos.second][currentPos.first] + 1 >= fireDist[newY][newX]) continue; // 이미 불이 지나간 곳이면서 지훈이가 불보다 늦게 도착했다면

			jihunDist[newY][newX] = jihunDist[currentPos.second][currentPos.first] + 1; // 새로 이동할 위치에 대해 거리 + 1
			jihunQueue.push(make_pair(newX, newY));
		}
	}

	cout << "IMPOSSIBLE"; // 지훈이 BFS에서 리턴 못 만났으면 탈출 못 한거
}

for (int i = 0; i < R; i++) { // dist 배열들 -1로 초기화	
    fill(jihunDist[i], jihunDist[i] + C, -1);
    fill(fireDist[i], fireDist[i] + C, -1);
}

for (int i = 0; i < R; i++)
    cin >> maze[i];

queue<pair<int, int>> jihunQueue;
queue<pair<int, int>> fireQueue;
for (int i = 0; i < R; i++) { // 지훈, 불 시작 위치 찾기 & 초기화
    for (int j = 0; j < C; j++)
    {
        if (maze[i][j] == 'F') {
            fireQueue.push(make_pair(j, i)); // (x, y)
            fireDist[i][j] = 0;
        }
        if (maze[i][j] == 'J') {
            jihunQueue.push(make_pair(j, i)); // (x, y)
            jihunDist[i][j] = 0;
        }
    }
}

거리 배열을 모두 -1로 초기화 한 후, 미로를 입력 받는다. 그리고 지훈이와 불의 시작점을 미리 알아야 하므로 불과 지훈이의 큐를 미리 선언한다. 여기서 주목할 점은 서로 종류가 다른 BFS이므로 큐와 거리 배열을 각자 만든다는 것이다. 그러고 나서 배열 전체를 돌다가 불과 지훈이를 찾은 경우 각각의 좌표를 각자의 큐에 집어넣고, 각자의 거리 배열의 값을 0으로 만들어준다.

// 불 먼저 BFS
while (!fireQueue.empty()) {
    auto currentPos = fireQueue.front(); fireQueue.pop(); // 큐의 앞에서 pop
    for (int i = 0; i < 4; i++) {
        int newX = currentPos.first + dx[i];
        int newY = currentPos.second + dy[i];

        if (newX < 0 || newX >= C || newY < 0 || newY >= R) continue; // 범위 체크
        if (fireDist[newY][newX] >= 0 || maze[newY][newX] == '#') continue; // 이미 방문한 곳 or 벽이면 체크

        fireDist[newY][newX] = fireDist[currentPos.second][currentPos.first] + 1; // 새로 이동할 위치에 대해 거리 + 1
        fireQueue.push(make_pair(newX, newY));
    }
}

여기서 중요한 점이 하나 더 있다. 두 종류의 BFS 중 독립적인 BFS를 먼저 실행해야 한다!  불에 관한 BFS는 이전 예제처럼 함수를 사용하지 않았던 점만 제외하면 모두 같은 내용이므로 설명하지 않겠다.

// 지훈이 BFS
while (!jihunQueue.empty()) {
    auto currentPos = jihunQueue.front(); jihunQueue.pop(); // 큐의 앞에서 pop
    for (int i = 0; i < 4; i++) {
        int newX = currentPos.first + dx[i];
        int newY = currentPos.second + dy[i];

        // 범위 벗어남 -> 탈출 성공
        // 큐에 거리순으로 들어가므로 탈출 성공한 곳 바로 출력
        if (newX < 0 || newX >= C || newY < 0 || newY >= R) {
            cout << jihunDist[currentPos.second][currentPos.first] + 1;
            return 0;
        }

        if (jihunDist[newY][newX] >= 0 || maze[newY][newX] == '#') continue; // 이미 방문 or 벽인 경우
        if (fireDist[newY][newX] != -1 && jihunDist[currentPos.second][currentPos.first] + 1 >= fireDist[newY][newX]) continue; // 이미 불이 지나간 곳이면서 지훈이가 불보다 늦게 도착했다면

        jihunDist[newY][newX] = jihunDist[currentPos.second][currentPos.first] + 1; // 새로 이동할 위치에 대해 거리 + 1
        jihunQueue.push(make_pair(newX, newY));
    }
}

cout << "IMPOSSIBLE"; // 지훈이 BFS에서 리턴 못 만났으면 탈출 못 한거

불에 대한 BFS가 모두 끝났다면 지훈이에 대한 BFS를 실행하면 된다. 여기에는 조건이 더 있으므로 자세하게 살펴보자.

// 범위 벗어남 -> 탈출 성공
// 큐에 거리순으로 들어가므로 탈출 성공한 곳 바로 출력
if (newX < 0 || newX >= C || newY < 0 || newY >= R) {
    cout << jihunDist[currentPos.second][currentPos.first] + 1;
    return 0;
}

지훈이는 가장자리에 있는 '.' 에서 탈출할 수 있으므로 범위 검사 부분에서 범위 바깥으로 나갔다면 탈출했다고 판단해 시작점으로부터 현재 위치까지의 거리를 출력한다.

if (fireDist[newY][newX] != -1 && jihunDist[currentPos.second][currentPos.first] + 1 >= fireDist[newY][newX]) continue;

불이 이미 지나간 곳 (fireDist[newY][newX]가 -1이 아님)이면서 지훈이가 현재 서있는 칸에서 인접한 칸으로 이동했을 때 걸리는 시간(jihunDist[currentPos.second][currentPos.first] + 1)이 불이 해당 칸을 지나간 시간(fireDist[newY][newX])보다 크거나 같다면 지훈이가 그 칸에 불과 동시에 도착했거나 이미 불이 지나간 곳을 방문한 것이므로 스킵한다.

 

만약 while문이 중간에 멈추지 않고 정상적으로 실행됐다면 지훈이가 탈출구를 찾지 못 한 것이므로 IMPOSSIBLE을 출력한다.

 

이런 종류의 BFS 문제를 처음 풀어봤다면 매우 어려웠을 것이다. 아무튼 이번 활용의 중요한 점을 다시 한 번 상기시키고 넘어가자.

• 거리 측정하는 BFS가 두 종류가 있다면, 거리 배열과 큐를 각각 만들어줘야 한다.
• 두 종류의 BFS에서 하나가 독립적인 경우, 독립적인 BFS를 먼저 실행하자.

BFS 활용 5 - 1차원 배열에서의 BFS

바로 예제로 들어가자. (https://www.acmicpc.net/problem/1697)

 

지금까지의 BFS는 2차원 배열에서 상하좌우로 움직이는 형태였는데, 이건 뭔가 다르다. 수빈이와 동생이 일직선 상에 있고, 그 위에서 움직인다. 그럼 다음과 같이 생각할 수 있다.

 

일직선 상에서 움직임 => 일차원 배열로 표현할 수 있음 => 2차원 배열에서 BFS가 상하좌우로 움직였으니까, 1차원 배열에서 좌우로만 움직이는 BFS를 사용해볼까?

 

이걸 바로 생각해 내기는 쉽지 않다... 1차원 배열에서 어떤 식으로 움직이는 지 살펴보자. 현재 위치는 밑줄, 다음에 이동할 수 있는 곳까지의 거리는 붉은색으로 표시했다.

 

수빈이는 X-1, X+1, 2X로 움직일 수 있다. 문제에 있는 예제처럼 수빈이가 5에 있고 동생이 17에 있다고 하자.

...	3	4	5	6	7	8	9	10	...
	-1	1	0	1	-1	-1	-1	1	...

수빈이는 5에 있으므로 시작점이 되는 5는 0이 된다. (초기 세팅) 그리고 이동할 수 있는 세 곳(X-1, X+1, 2X)까지의 거리를 계산해 저장하면서 큐에 집어넣는다. 모두 끝났다면 큐의 앞에 있는 값을 꺼내 그곳으로 이동한다.

...	3	4	5	6	7	8	9	10	...
	2	1	2	1	-1	2	-1	1	...

위와 같은 방식으로 계산한다. 이렇게 진행하다가 동생이 있는 17번 인덱스의 값이 -1이 아니게 되면 수빈이가 동생을 찾은 것이므로 17번 인덱스의 값을 출력 후 종료한다.

 

코드를 살펴보자.

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

int subinPos, brotherPos;
int dist[100001]; // 일직선상에서 수빈이가 처음 위치에서 움직여서 동생을 찾을 때까지의 거리
queue<int> q; // 다음으로 움직일 곳

void BFS() {
	while (!q.empty()) {
		int currentPos = q.front(); q.pop();

		for (int i = 0; i < 3; i++) {
			switch (i) {
				case 0: // X - 1
					if (currentPos - 1 < 0 || currentPos - 1 > 100000) break; // 범위
					if (dist[currentPos - 1] != -1) break; // 이동하지 않은 곳으로만 이동
					dist[currentPos - 1] = dist[currentPos] + 1;
					q.push(currentPos - 1);
					break;
				case 1: // X + 1
					if (currentPos + 1 < 0 || currentPos + 1 > 100000) break;
					if (dist[currentPos + 1] != -1) break;
					dist[currentPos + 1] = dist[currentPos] + 1;
					q.push(currentPos + 1);
					break;
				case 2: // 2 * X
					if (2 * currentPos < 0 || 2 * currentPos > 100000) break;
					if (dist[2 * currentPos] != -1) break;
					dist[2 * currentPos] = dist[currentPos] + 1;
					q.push(2 * currentPos);
					break;
			}
		}

		if (dist[brotherPos] != -1) return; // 동생 찾으면 종료
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> subinPos >> brotherPos;
	fill(dist, dist + 100001, -1); // -1로 초기화

	dist[subinPos] = 0;
	q.push(subinPos);
	BFS();
	
	cout << dist[brotherPos];
}

사실 이런 종류의 문제를 처음 봤다면 BFS인 것을 생각해 내기도 어려웠을 것이다. 이번 활용의 중요한 점인 1차원 배열에서 좌우로 움직이는 BFS를 사용할 수 있다는 것을 꼭 알고 있자.