[BOJ] 다리만들기

*dfs로 섬들을 라벨링 (섬이 3개면 라벨이 3까지 나와야 한다)

*섬 전체적으로 돌면서 바다(0)이 나오면 그 지점을 중심으로 다리를 건설한다. (buildBridge)

*다리 건설은 bfs로 탐색하는데, 만약 섬(1)을 만났는데 나와 같은 라벨을 가지고 있으면 이상한 방향으로 향하고 있다는 것이기 때문에 (내 섬을 주변으로 돌고 있음 ) 방향을 바꿔주고 (continue), 

만약 다른 라벨을 가지고 있는 섬을 만났다면 그곳까지의 거리를 반환한다. 

 

 

#include <iostream> #include <vector> #include <queue> #include <cstring> #include <functional> #define INF 10000 using namespace std; int n; int map[102][102], labelMap[102][102]; bool visited[102][102]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; typedef pair<int, int> pp; typedef pair<int, pp> ipp; int buildbridge(int x, int y) { queue<pp> q; q.push(pp(x, y)); visited[x][y] = true; int res = INF, cnt = 0; while (!q.empty()) { int size = q.size(); while (size--) { int cx = q.front().first; int cy = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) { continue; } visited[nx][ny] = true; //같은 지역을 다시 만나면 false if (map[nx][ny]) { if (labelMap[nx][ny] == labelMap[x][y]) { continue; } else { res = min(res, cnt); continue; } } q.push( pp(nx, ny)); } } cnt++; } return res; } void dfs(int x, int y, int label) { if (visited[x][y]) return; visited[x][y] = true; labelMap[x][y] = label; 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 || visited[nx][ny] || !map[nx][ny]) { continue; } dfs(nx, ny, label); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; } } int label = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j] && map[i][j]) { ++label; dfs(i, j, label); } } } int ans = INF; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j]) { memset(visited, 0, sizeof(visited)); visited[i][j] = true; //섬의 가장자리로 간다. int res = buildbridge(i, j); ans = min(ans, res); } } } cout << ans << '\n'; return 0; }