[백준]Baekjoon2146(DFS,BFS)

문제 링크 : https://www.acmicpc.net/problem/2146

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int map[100][100]; //지도
int group[100][100]; //섬 별로 그룹화한 모습
int dist[100][100]; //거리

int N; //지도의 크기
int cnt = 0; //그룹화 하기위한 변수

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
 
void grouping(int x, int y) { //BFS를 통해 각각의 섬을 그룹화 한다.
	group[x][y] = ++cnt; //첫번째 좌표 group값 cnt로 설정
	dist[x][y] = 0; //dist값은 0으로 설정
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));

	while (!q.empty())
	{
		x = q.front().first;
		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) {
				if (map[nx][ny] == 1 && dist[nx][ny] == -1) { //섬이면서 아직 검사되지 않은 좌표라면
					group[nx][ny] = cnt; //cnt로 그룹화
					dist[nx][ny] = 0; //섬 자체의 dist는 0으로 초기화
					q.push(make_pair(nx, ny));
				}
			}
		}
		
	}
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			dist[i][j] = -1; //초기화
			group[i][j] = -1;
		}
	}

	queue<pair<int, int>> q;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1 && dist[i][j] == -1)
				grouping(i, j); //그룹핑

			if (dist[i][j] == 0) q.push(make_pair(i, j)); 
			//섬이 있는 좌표에 대해서 queue에 삽입
		}
	}

	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) {
				if (dist[nx][ny] == -1) { //만약 (nx,ny)가 탐색되지 않은 좌표라면
					group[nx][ny] = group[x][y]; //현재 좌표의 그룹과 같은 그룹이라고 설정
					dist[nx][ny] = dist[x][y] + 1; //거리는 현재 좌표의 거리 + 1
					q.push(make_pair(nx, ny));
				}
			}
		}
	}

	int result = -1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];

				if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
					if (group[i][j] != group[nx][ny]) { //근처에 있는 좌표가 같은 그룹에 속하는 것이 아니라면
						if (result == -1 || dist[i][j] + dist[nx][ny] < result) 
							result = dist[i][j] + dist[nx][ny];
					}// 그 두 좌표에 기록되어있는 거리를 더한것이 섬 사이의 거리이며 그 중에 최솟값을 저장한다.
				}
			}
		}
	}

	printf("%d\n", result);
}