[백준/BOJ] 2146번 다리 만들기 (C++)

www.acmicpc.net/problem/2146

2146번: 다리 만들기

구현 부분에서 조금 애먹었지만 풀이 로직은 정확하게 맞은 문제

1년 후에 다시 풀었더니 한번에 맞췄다. ㅎㅎ

 

BFS를 두번 사용해야하는데, 첫번째 BFS는 각 섬의 영역에 번호를 매기기 위해 사용하고, 두번째 BFS는 각 섬에서 다른 섬까지의 최소 거리를 구하는데 사용해서 문제를 해결했다.

 

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

struct Pos {
	int x, y, d;
};

int n, answer = INT_MAX;
int map[101][101];
bool visit[101][101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int, int> > v;

int second_BFS(int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy, 0 });
	visit[sx][sy] = true;
	int pivot = map[sx][sy];
	
	while(!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		q.pop();
		
		if(map[x][y] != 0 && map[x][y] != pivot) return d - 1; 
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx < n && ny >= 0 && ny < n && !visit[nx][ny] && map[nx][ny] != pivot) {
				q.push({ nx, ny, d + 1 });
				visit[nx][ny] = true;
			}
		} 
	}
	
	return INT_MAX;
}
 
void first_BFS(int sx, int sy, int num) {
	queue<pair<int, int> > q;
	q.push({ sx, sy });
	visit[sx][sy] = true;
	map[sx][sy] = num;
	v.push_back({ sx, sy });
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx < n && ny >= 0 && ny < n && !visit[nx][ny] && map[nx][ny] == 1) {
				q.push({ nx, ny });
				visit[nx][ny] = true;
				map[nx][ny] = num;
				v.push_back({ nx, ny });
			}
		}
	}
}

int main(void) {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	
	int num = 1;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(!visit[i][j] && map[i][j] == 1) {
				first_BFS(i, j, num);
				num++;
			} 
		}
	}
	
	memset(visit, false, sizeof(visit));
	for(int i = 0; i < v.size(); i++) {
		answer = min(answer, second_BFS(v[i].first, v[i].second));
		memset(visit, false, sizeof(visit));
	}
	
	cout << answer;
}