백준 2146 다리 만들기

www.acmicpc.net/problem/2146

2146번: 다리 만들기

처음엔 완전 탐색으로 다리를 전부 놓으면서 최적의 수를 찾는 줄 알았다.

알고리즘 분류를 보니 BFS, DFS여서 어떻게 해야 할지 감이 잘 안 잡혔다.

 

1. 1차 BFS를 통해 대륙의 번호를 지정해준다.

2. 큐에 땅의 위치를 전부 삽입해준다

3. BFS를 한번 더 돌려서 이동 범위가 바다라면 큐에 삽입해준다

4. 이동 범위가 땅인데 대륙 번호가 같지 않다면 거기까지의 거리를 리턴해준다.

 

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

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define X first
#define Y second
#define f(i,n) for(int i=0;i<n;i++)

int n, ar[101][101];
bool vis[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
vector<pair<int, int>> V;

void init() {
	f(i, 101) fill(vis[i], vis[i] + 101, false);
}

void numbering(int x, int y, int num) {
	queue<pair<int, int>> Q;
	Q.push({ x,y }); vis[x][y] = true;
	ar[x][y] = num;
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		f(i, 4) {
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (!vis[nx][ny] && ar[nx][ny] == -1) {
				Q.push({ nx,ny }); vis[nx][ny] = true; ar[nx][ny] = num;
			}
		}
	}
}

int bfs(int num) {

	//다리 놓는 BFS 하기전 땅을 전부 큐에 넣어주고 그 땅에서 바다라면 큐에 삽입
	//땅인데 같은 넘버가 아니라면 종료해준다.

	queue<pair<int, int>> Q;
	f(i, n) {
		f(j, n) {
			if (ar[i][j] == num) {
				Q.push({ i,j }); vis[i][j] = true;
			}
		}
	}

	int ret = 0;
	while (!Q.empty()) {
		int len = Q.size(); //큐 사이즈만큼 돌려야 런타임 에러를 피할듯
		f(i, len) {
			auto cur = Q.front(); Q.pop();
			f(dir, 4) {
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (ar[nx][ny] != 0 && ar[nx][ny] != num) return ret;
				else if (ar[nx][ny] == 0 && !vis[nx][ny]) {
					//cout << "Check" << '\n';
					vis[nx][ny] = true; Q.push({ nx,ny });
				}
			}
		}
		ret++;
		//cout << "RET= " << ret << '\n';
	}
}

int main() {
	fast;

	cin >> n;
	f(i, n) {
		f(j, n) {
			cin >> ar[i][j];
			if (ar[i][j] == 1) {
				ar[i][j] = -1;
				V.push_back({ i,j });
			}
		}
	}
	int num = 1;
	for (int i = 0; i < (int)V.size(); i++) {
		auto cur = V[i];
		if (!vis[cur.X][cur.Y]) {
			numbering(cur.X, cur.Y, num); num++;
		}
	}

	////To Numbering Check
	//cout << endl;
	//f(i, n) { f(j, n) { cout << ar[i][j] << ' '; }cout << '\n'; }

	int ans = 1e9;
	for (int i = 1; i < num; i++) {
		init();
		//cout << "ans = " << ans << '\n';
		ans = min(ans, bfs(i));
	}
	cout << ans << endl;

	return 0;
}

 

이런 그래프 문제는 경우의 수마다 맵을 출력 해보며 오차범위를 찾는 게 가장 좋은 것 같다.

이번에도 nx를 ny로 써서 몇 번은 틀렸다 ㅜ.