[baekjoon 2146] 다리 만들기 (그래프, BFS) (C++)

www.acmicpc.net/problem/2146

2146번: 다리 만들기

주어진 섬들 중에 최단 경로를 구하면 되는 문제이다. 

처음에 어떻게 풀면 할까, 하다가 N이 최대 100이길래 완전 탐색 느낌으로 거리를 구하면 되겠다.라고 생각했다.

 

내 풀이법은 일단

1. BFS를 통해서 연결된 섬에 대한 정보를 얻는다.

2. 이후에 vector<pair<int, int>> v[5001]의 2차원 벡터에 땅 하나에 맞춰서 벡터에 좌표를 넣어준다.

ex) 첫 번째 BFS 수행 -> 첫 번째 땅 탐색이므로 v[0]에 좌표값들 (1,1), (1,2) 등을 넣어준다.

 

3. 그렇게 섬에 대한 정보를 저장한 다음에, 섬의 좌표들끼리 거리를 계산해서 최솟값을 출력하는 것이다.

4중 for문으로 약간 무식하게 풀었지만, N이 작기 때문에 오히려 다른 풀이들보다 0.52ms로 시간도 괜찮게 나왔다.

ex) 첫 번째 땅과 두 번째 땅끼리 최단거리 비교(v[0]과 v[1]에 저장된 pair 좌표들끼리 계산)

-> 첫 번째 땅과 세 번째 땅 계산 ... 마지막 땅까지

-> 두 번째부터 마지막까지... N-1 땅에서 N까지 계산해준다.

 

+ BFS 함수 마지막 부분에서

			if (!check[x][y] && field[x][y]) {
				if (x >= 0 && y >= 0 && x < N && y < N) {
					q.push(make_pair(x, y));
					check[x][y] = true;
					int temp = 1;
					for (int i = 0; i < 4; i++) {
						int xX = x + xmove[i];
						int yY = y + ymove[i];
						if(xX >= 0 && yY >= 0 && xX < N && yY < N)
							temp *= field[xX][yY];
					}
					if(temp == 0)
						v[cnt].push_back(make_pair(x, y));

 원래는 그냥 모조리 v[cnt]에 섬의 좌표를 넣었는데, 질문을 보니 사람들이 섬의 외곽 좌표만 계산하는 것을 보았다.

그게 훨씬 효율적일것이라고 생각해서 넣은 코드이다.

기준 좌표에서 상하좌우에 0(바다 값)이 있으면 한 번이라도 곱하면 0이 되기 때문에 영역 내의 상하좌우를 곱해서 최종 값이 0이면 외곽 좌표이므로 그때 v[cnt]에 넣어주었다.

(그런데 그냥 모든 좌표 모조리 넣어서 거리 계산했을 때랑 시간 똑같이 나왔다.)

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

int N, field[101][101], check[101][101];
vector<pair<int, int>> v[5001];

int xmove[4] = { 1, -1, 0, 0 }, ymove[4] = { 0,0,1,-1 };

void BFS(int cnt, int startX, int startY) {
	v[cnt].push_back(make_pair(startX, startY));
	queue<pair<int, int>> q;
	q.push(make_pair(startX, startY));
	check[startX][startY] = true;

	while (!q.empty()) {
		int tempX = q.front().first;
		int tempY = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int x = tempX + xmove[i];
			int y = tempY + ymove[i];

			if (!check[x][y] && field[x][y]) {
				if (x >= 0 && y >= 0 && x < N && y < N) {
					q.push(make_pair(x, y));
					check[x][y] = true;
					int temp = 1;
					for (int i = 0; i < 4; i++) {
						int xX = x + xmove[i];
						int yY = y + ymove[i];
						if(xX >= 0 && yY >= 0 && xX < N && yY < N)
							temp *= field[xX][yY];
					}
					if(temp == 0)
						v[cnt].push_back(make_pair(x, y));
				}
			}
		}
	}
}

int cal(pair<int, int> & a, pair<int, int> & b) {
	return (abs(a.first - b.first) + abs(a.second - b.second))-1;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> field[i][j];
		}
	}
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!check[i][j] && field[i][j]) {
				BFS(count, i, j);
				count++;
			}
		}
	}

	int m = 987654321;

	for (int i = 0; i < count; i++) {
		for (int j = i + 1; j < count; j++) {
			for (int k = 0; k < v[i].size(); k++) {
				for (int g = 0; g < v[j].size(); g++) {
					m = min(m, cal(v[i][k], v[j][g]));
				}
			}
		}
	}
	cout << m;
	return 0;
}

 처음에 OutOfBounds 런타임 에러를 받았는데 땅이 총 100 * 100 이므로 나올 수 있는 섬의 최대 개수는 5000개이다. (10000개의 영토에 한 칸씩 띄어서 있는 경우)

그래서 v[5001]를 했어야 했는데 처음에 아무 생각 없이 v[101]로 해서 틀렸다.