[백준] 2146번 다리 만들기 by C++

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

2146번: 다리 만들기

어렵지 않게 풀 수 있을 줄 알았는데, 생각보다 시간이 너무 걸렸다.

 

 

핵심 변수

 qBuf - 1번째 BFS의 queue

 q - 2번째 BFS의 queue

qSize - 2번째 BFS에서 각 시행 횟수

answer - 대륙간의 최단 거리

 

 

알고리즘 방식

전체적으로 2번의 BFS알고리즘을 사용하는데,

1번째 BFS

 대륙에 번호를 매기고, pair<int, int> vis 배열에 {1, 대륙 번호}를 입력하며,

 각 좌표와 대륙 번호를 queue<pair<int, int>, int>> q에 {{i, j}, 대륙 번호}의 형태로 저장한다.

 

2번째 BFS

 모든 대륙에서 바다쪽으로 1칸씩 나아가며 vis.first의 값을 1씩 증가시킨다.

   (vis.first는 대륙과 바다 사이의 거리 - 1 // 대륙의 vis.first가 1이므로 1을 빼주어야 거리가 됨)

 만약 1칸 이동했을 때, 해당 바다를 대륙에서 먼저 접근했고(vis.first != 0), 그 대륙이 지금과 다른 대륙이라면

  (vis.second의 대륙 번호를 통해 판별), 두 개의 vis.first 값을 통해 두 대륙간의 거리를 구한다.

 

 이 다음이 핵심인데, 먼저 생각해 볼 것이 있다.

  1차원으로 1 0 0 1 인 나라와 1 0 0 0 1인 나라가 있다고 가정하자.

  처음으로 한칸 씩 나아간 후의 vis.first는

                   1 2 2 1                 1 2 0 2 1이며, 

  이 결과까지는, BFS를 통해 옆에 대륙이 있는지 없는지를 판단할 수 없다. 

  다시 한 칸씩 대륙에서 바다로 나아가면, 두 나라 모두 옆에 대륙이 있음을 확인 할 수 있다.

  (               1 2 2 1                 1 2 3 2 1 // 첫 번째 나라의 경우 1번째 2가 2번째 2를 찾음

                                                                두 번째 나라의 경우  1번째 2가 3을 생성하고, 2번째 2가 3을 찾음)

  두 대륙 모두 2번째 시행에서 대륙간의 거리를 구할 수 있는데, 각 거리는 2와 3으로 다르다.

  다시 문제로 돌아와서, 두 대륙간에 거리가 2(짝)와 3(홀)인 지점이 존재하고,

   해당 지점을 구하는 순간 BFS를 종료 시켜버리면, 3인 지점이 먼저 탐색될 경우, 잘못된 결과를 초래한다.

   따라서, BFS를 진행하기 전에, 해당 시행(각 대륙에서 1칸 씩)의 개수(q.size())를 저장하고,

  이를 통해 2번째 BFS의 시행을 세분화 하여, 해당 시행을 모두 실행한 후에 최단 거리가 존재한다면, 이를 결과로 출력한다.

 

 

소스코드

//반례
//5
//1 0 0 0 1
//0 0 0 0 0
//0 0 0 0 0
//0 0 0 0 0
//0 1 0 0 1
//
//answer = 2;

#include <iostream>
#include <queue>

using namespace std;

int board[100][100];
pair<int, int> vis[100][100];

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

queue<pair<pair<int, int>, int>> qBuf;
queue<pair<pair<int, int>, int>> q;
int N;

int BFS() {
	int landCount = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 1 && vis[i][j].first == 0) {
				vis[i][j] = {1, landCount};
				qBuf.push({ {i, j}, landCount });
				q.push({ {i, j}, landCount++ });

				while (!qBuf.empty()) {
					pair<pair<int, int>, int> cur = qBuf.front();
					qBuf.pop();

					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.first.first + dx[dir];
						int ny = cur.first.second + dy[dir];

						if (nx < 0 || nx >= N || ny < 0 || ny >= N)
							continue;

						if (board[nx][ny] == 1 && vis[nx][ny].first == 0) {
							vis[nx][ny] = { 1, cur.second };
							qBuf.push({ {nx, ny}, cur.second });
							q.push({ {nx, ny}, cur.second });
						}
					}
				}
			}
		}
	}
	int answer = 200;
	while (!q.empty()) {
		int qSize = q.size();

		while (qSize--) {
			pair<pair<int, int>, int> cur = q.front();
			q.pop();

			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.first.first + dx[dir];
				int ny = cur.first.second + dy[dir];

				if (nx < 0 || nx >= N || ny < 0 || ny >= N)
					continue;

				if (board[nx][ny] == 0 && vis[nx][ny].first == 0) {
					vis[nx][ny] = { vis[cur.first.first][cur.first.second].first + 1, vis[cur.first.first][cur.first.second].second };
					q.push({ {nx, ny}, cur.second });
				}
				else if (board[nx][ny] == 0 && vis[nx][ny].first <= vis[cur.first.first][cur.first.second].first + 1 && vis[nx][ny].second != cur.second) {
					int length = vis[nx][ny].first + vis[cur.first.first][cur.first.second].first - 2;
					if (answer > length)
						answer = length;
				}
			}
		}
		if (answer != 200)
			return answer;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}



	cout << BFS() << '\n';

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << vis[i][j].first << ' ';
		}
		cout << '\n';
	}
}