백준 Baekjoon 2146 다리만들기 풀이

사용언어

Visual studio 2019 C++

문제 간단요약

각각의 섬중 가장 가까운 두 섬의 거리차 구하기

생각하기

각각의 섬을 다른 숫자로 지정하기 DFS와 BFS 사용하기

[2146 풀이]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX = 100;
int N;
int arr[MAX][MAX];
int gogoA[4] = { 0,1,0,-1 };
int gogoB[4] = { 1,0,-1,0 };
bool visited[MAX][MAX];

void numbering(int a, int b, int cnt) {
	visited[a][b] = true;
	arr[a][b] = cnt;

	for (int i = 0; i < 4; i++) {
		int A = a + gogoA[i];
		int B = b + gogoB[i];
		if (A >= 0 && A < N && B >= 0 && B < N)
			if (arr[A][B] && !visited[A][B]) // 방문하지 않았고 0이아닌곳이라면
				numbering(A, B, cnt);
	}
}

int counting(int cnt) {
	queue<pair<int, int>> q;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (arr[i][j] == cnt && !visited[i][j]) { // cnt번째 섬이고 방문하지 않았다면
				visited[i][j] = true;
				q.push(make_pair(i, j));
			}
	int result = 0;
	while (!q.empty()) {
		int qsize = q.size();
		for (int i = 0; i < qsize; i++) {
			int a = q.front().first;
			int b = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				int A = a + gogoA[i];
				int B = b + gogoB[i];

				if (A >= 0 && A < N && B >= 0 && B < N) {
					if (arr[A][B] && arr[A][B] != cnt)
						return result;
					else if (!arr[A][B] && !visited[A][B]) {
						visited[A][B] = true;
						q.push(make_pair(A, B));
					}
				}
			}
		}
		result++; // 한번의 qsize가 돌때마다 +1해줌
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];
	int cnt = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited[i][j] && arr[i][j]) // 1이고 방문하지 않았다면
				numbering(i, j, cnt++); // cnt번째 섬
		}
	}
	int result = 99999999;
	for (int i = 1; i < cnt; i++) {
		memset(visited, false, sizeof(visited));
		result = min(result, counting(i)); // i번째 섬에서 가장 거리가 가까운 counting(i)
	}
	cout << result << "\n";
}