[BOJ] 2146번 다리 만들기(C++)

POINT

좌표상에 랜덤으로 배치된 덩어리들 사이의 최단 경로를 구해야 하는 문제였다. 덩어리 사이의 거리를 구하는 방식은 다른 문제에도 활용될 가능성이 높다고 생각되어, 정리를 하고 넘어가야겠다.

덩어리의 번호를 정해준다.

기본 육지의 값은 1로 Input 되지만 이것을 -1 로 바꿔준다. 왜냐면 덩어리의 번호를 1 부터 시작할 것이기 때문이다. Land() 메소드를 제작하여 덩어리에 Label 을 색칠해준다.

한 덩어리에서 다른 덩어리까지의 거리를 구하는 방법

우선 한 덩어리의 모든 좌표를 Queue 에 집어넣고, 그 좌표를 Visit = 1 처리 해버리는 것이다. 나는 문제를 보면서 "이걸 다 BFS 를 돌리면 무조건 시간초과가 발생할텐데" 라는 생각을 했지만 애초에 모든 좌표를 Queue 에 집어넣고 방문처리를 해두면, 중복 탐색의 여지가 방지되는것이다. 꼭 외워둬야겠다.

별개로

만약 임의의 덩어리까지의 최단거리가 아닌, 정해진 덩어리까지의 거리를 구하려고 해도 같은 방식을 사용할 수 있다. BFS() 메소드의 조건문에 이를 추가하면 같은 알고리즘으로도 조건에 맞는 결과값을 반환할 수 있다.

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int N;
int Map[101][101];
int Visit[101][101];

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int Ans = 9999;

void Clear() {
	memset(Visit, 0, sizeof(Visit));
}

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> Map[i][j];
			if (Map[i][j] == 1)
			{
				Map[i][j] = -1;
			}
		}
	}
}

void Land(int x, int y, int Label) {
	
	queue<pair<int, int>> Q;
	Q.push({ x, y });
	Map[x][y] = Label;
	
	while (!Q.empty())
	{
		int px = Q.front().first;
		int py = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = px + dx[i];
			int ny = py + dy[i];

			if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
			if (Visit[nx][ny] == 1) continue;
			if (Map[nx][ny] == -1)
			{
				Visit[nx][ny] = 1;
				Map[nx][ny] = Label;
				Q.push({ nx, ny });
			}
			
		}
		
	}
}

int Bfs(int num) {
	
	queue<pair<pair<int, int>, int>> Q;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (Map[i][j] == num)
			{
				Q.push({ {i, j}, 0 });
				Visit[i][j] = 1;
			}
		}
	}
	// num 영역을 모두 push

	while (!Q.empty())
	{
		int px = Q.front().first.first;
		int py = Q.front().first.second;
		int time = Q.front().second;
		Q.pop();

		if (Map[px][py] != 0 && Map[px][py] != num)
		{
			return time - 1;
		}

		for (int i = 0; i < 4; i++)
		{
			int nx = px + dx[i];
			int ny = py + dy[i];

			if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
			if (Visit[nx][ny] == 1) continue;
			
			Visit[nx][ny] = 1;
			Q.push({ {nx, ny}, time + 1 });
		}
	}

	return -1;

}


int main() {

	Input();
	int Label = 1;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (Visit[i][j] == 0 && Map[i][j] == -1)
			{
				Visit[i][j] = 1;
				Land(i, j, Label);
				Label++;
			}
		}
	}

	Clear();
	//대륙 번호 지정

	for (int i = 1; i < Label; i++)
	{
		int Curr = Bfs(i);
		Ans = min(Ans, Curr);
		Clear();
	}

	cout << Ans;

}