백준 2146번: 다리 만들기 (C++)

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

2146번: 다리 만들기

 

dfs와 bfs를 모두 활용한다.

 

dfs를 통해서 섬의 개수를 파악하고, 섬마다 index를 할당해준다.

 

이후에는 섬으로부터 바다로 탐색을 수행하고, 이때 bfs를 활용한다.

 

거리를 측정하기 시작한 섬에 대한 정보를 idx 배열에 저장해준다.

 

즉 i행 j열이 바다라고 한다면, 섬이 아니기 때문에 index가 할당되어있지 않은데, 

 

어느 섬으로부터 측정한 거리라는 것을 idx 배열에 명시해준다.

 

이를 통해서 다른섬이 만났을 때, 그 지점까지의 거리가 만들 수 있는 다리의 최소 거리인지 판단해준다.

 

#include<iostream>
#include<queue>
using namespace std;
int m[100][100], n, dis[100][100], idx[100][100];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int Min = -2;

queue <pair<int, int> > q;
void init() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dis[i][j] = -1;
	while (!q.empty()) q.pop();
}
void minCal(int val) { //최소 거리인지 판단
	if (Min == -2) { //최솟값이 갱신된 적이 없다면
		Min = val;
		return;
	}
	else {
		if (Min > val) Min = val;
		else
			return;
	}
}
bool boundCheck(int r, int c) {
	return r < 0 || c < 0 || r >= n || c >= n;
}
void dfs(int row, int col, int landCnt) {
	dis[row][col]++;
	idx[row][col] = landCnt; //섬의 index 지정
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		if (boundCheck(nr, nc) || m[nr][nc] == 0 || dis[nr][nc] >= 0) continue;
		dfs(nr, nc, landCnt);
	}
}
void bfs(pair<int, int> start) {
	q.push(start);
	dis[start.first][start.second]++;

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (boundCheck(nr, nc) || dis[nr][nc] >= 0) continue;
			if (m[nr][nc] == 1) {
				//섬을 만났을 때
				if (idx[nr][nc] == idx[cur.first][cur.second]) continue;
				else {
					//출발한 섬과 다른 섬을 만났을 때
					minCal(dis[cur.first][cur.second]);
					init();
					return;
				}
			}
			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
			idx[nr][nc] = idx[cur.first][cur.second];
			//어느 섬에서 측정한 거리라는 것을 명시
		}
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	init();
	
	int landCnt = 0; // 섬 번호
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] < 0 && m[i][j] == 1) {
				landCnt++;
				dfs(i, j, landCnt);
			}
		}
	}
	init(); //방문처리 배열 초기화

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] < 0 && m[i][j] == 1) {
				bfs({ i, j });
			}
		}
	}
	cout << Min << '\n';
	return 0;
}
//섬과 섬을 잇는 가장 짧은 다리
//1에서 시작해서 0으로 퍼져나가게
//퍼져나가기 시작한 점이 어느 섬인지 확인하면서 비교

//dfs로 섬 개수 파악하고 번호 매김
//섬이면서 방문 안 한 곳 bfs -> 주변이 바다인 곳 방문(거리측정)
//가다가 섬이면서 내 섬이 아닌 곳을 만나면 중지 -> 길이 최소 비교