백준 2146번:다리 만들기

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

2146번: 다리 만들기

이 문제는 각 섬마다 그룹화가 필요하다. 그 이유는 최단 거리를 구하기 위해서 DFS를 이용해야 하는데 그냥 돌려버리면

최단거리가 아닌 각 섬에서 출발하여 중간에서 만나는 거리가 구해지기 때문이다. 즉 섬마다 그룹을 나눈다음에 각 섬끼리의 최단거리를 각각 구해야한다.

즉 이 문제는  DFS를 각 섬의 개수만큼 돌려서 최단거리를 구하면 된다.

#include<iostream>
#include <queue>
#include <cstdio>
using namespace std;
#pragma warning(disable : 4996)
int px[4] = { 0,0,1,-1 };    
int py[4] = { 1,-1,0,0 }; 
int d[100][100];                     //값 넣기
int sum[100][100];                   //BFS를 진행할때 거리 계산할 용도
int grp[100][100];                   //그룹화를 할 배열
int cnt = 1;                         //섬의 그룹번호 지정을 위한 변수
int m;
void dfs(int x, int y) {               //섬의 그룹화를 위한 dfs
	grp[x][y] = cnt;
	for (int k = 0; k < 4; k++) {
		int nx = x + px[k];
		int ny = y + py[k];
		if (0 <= nx && nx < m && 0 <= ny && ny < m) {
			if (grp[nx][ny] == 0 && d[nx][ny] == 1) {
				dfs(nx, ny);
			}
		}
	}
}
int main() {


	cin >> m;

	for (int i = 0; i < m; i++) {
		for (int k = 0; k < m; k++) {
			scanf("%1d", &d[i][k]);
		}
	}
	for (int i = 0; i < m; i++) {                        //그룹번호 지정
		for (int k = 0; k < m; k++) {
			if (grp[i][k] == 0 && d[i][k] == 1) {
				dfs(i, k);
				cnt++;
			}
		}
	}
	int ans = -1;
	for (int l = 1; l < cnt; l++) {
		queue<pair<int, int>> q;
		for (int i = 0; i < m; i++) {
			for (int k = 0; k < m; k++) {
				sum[i][k] = -1;                   //섬이 아니면 -1대입
				if (grp[i][k] == l) {
					sum[i][k] = 0;               //섬이면 0대입
					q.push(make_pair(i, k));
				}
			}
		}
		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 + px[i];
				int ny = y + py[i];
				if (0 <= nx && nx < m && 0 <= ny && ny < m) { //한개의 섬을 기준으로 모든 거리 값 구하기
					if (sum[nx][ny] == -1) {                
						sum[nx][ny] = sum[x][y] + 1;         
						q.push(make_pair(nx, ny));
					}
				}
			}
		}
		for (int i = 0; i < m; i++) {
			for (int k = 0; k < m; k++) {
				if (d[i][k] == 1 && grp[i][k] != l) {         //섬이면서 다른 섬인경우
					if ((ans == -1) || (sum[i][k] - 1 < ans)) {  //최단거리 구하기
						ans = sum[i][k] - 1;
					}
				}
			}
		}
	}
	cout << ans;
	return 0;
}