백준 2146 다리만들기

문제링크

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

문제

풀이

1. 섬과 섬의 구분을 위해 각 섬에서 bfs를 이용해 넘버링을 해주었습니다.

2. 모든 섬에 대해 다시 bfs를 실행해 다른 섬에 도착하는 최단 거리를 측정 하였습니다.

---

시행착오

없었습니다.

---

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n, maps[101][101];
int dx[4]{ 0,0,1,-1 };
int dy[4]{ 1,-1,0,0 };
bool vi[101][101];
queue<pair<int, int>> q,q2[10001];
void numbering(int i, int j,int idx) {
	q.push({ i,j });
	q2[idx].push({ i,j });
	maps[i][j] = idx;

	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) continue;
			if (maps[nx][ny] == -1) {
				q.push({ nx,ny });
				q2[idx].push({ nx,ny });
				maps[nx][ny] = idx;
			}
		}
	}
}

int calc_dist(int idx) {

	fill(&vi[0][0], &vi[100][101], false);

	int dist = 0;
	while (!q2[idx].empty()) {
		int sz = q2[idx].size();
		for (int k = 0; k < sz; k++) {
			int x = q2[idx].front().first;
			int y = q2[idx].front().second;
			q2[idx].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) continue;
				if (vi[nx][ny]) continue;
				if (maps[nx][ny] == 0) {
					vi[nx][ny] = true;
					q2[idx].push({ nx,ny });
					continue;
				}

				if (maps[nx][ny] != idx) return dist;
				
			}
		}
		dist++;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maps[i][j];
			if (maps[i][j] == 1) maps[i][j] = -1;
		}
	}

	int idx = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (maps[i][j] == -1) {
				numbering(i, j, idx);
				idx++;
			}
		}
	}

	int ans = 201;
	for (int i = 1; i < idx; i++) {
		ans = min(ans, calc_dist(i));
	}
	cout << ans;
}

---

후기