[백준/BOJ] 백준 2146번 : 다리 만들기

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

2146번: 다리 만들기

dfs를 통해 각 대륙마다 번호를 칠한다(번호는 2부터 칠한다). 그리고 그 대륙의 끝 지점 들을 따로 저장해둔다. 그리고 난 뒤 bfs를 통해 각 대륙에서 다른 대륙으로 가는 가장 가까운 거리를 구하고 그중 최소 거리를 찾는다.

 

코드

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

int n;
int board[100][100];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
vector<pair<int, int>> end_point_list[10002];
int visited[100][100];
int discoverd[100][100];
int depth[100][100];

//here지역과 같은 대륙을 are_number로 체크한다
void numberCheck(pair<int,int> here, int area_number)
{
	visited[here.first][here.second] = 1;
	board[here.first][here.second] = area_number;

	//here지점이 are_number의 끝 지점인지 확인
	bool end_point = false;
	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] == 0)
		{
			end_point = true;
			break;
		}
	}

	//here지점이 are_number대륙의 끝지점이라면 따로 저장해둔다(나중에 다른 대륙과 거리 측정에 사용하기 위해)
	if (end_point)
	{
		end_point_list[area_number].push_back(here);
	}

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] == 1 && visited[there.first][there.second] == 0)
		{
			numberCheck(there, area_number);
		}
	}
}

//area_number 대륙부터 다른 대륙으로 이어지는 가장짧은 거리를 찾는다
int Solve(vector<pair<int, int>> end_point, int area_number)
{
	queue<pair<int, int>> q;

	//are_number대륙의 끝 지점들을 큐에 넣어 bfs를 진행한다
	for (int i = 0; i < end_point.size(); i++)
	{
		discoverd[end_point[i].first][end_point[i].second] = 1;
		depth[end_point[i].first][end_point[i].second] = 0;
		q.push(end_point[i]);
	}

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//다른 대륙에 도착 했을때 현재 지점 깊이의 -1이 여기까지 오는데 거리이다
		if (board[here.first][here.second] != 0 && board[here.first][here.second] != area_number)
			return depth[here.first][here.second] - 1;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] != area_number && discoverd[there.first][there.second] == 0)
			{
				discoverd[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;
				q.push(there);
			}
		}
	}

	return -1;
}

//초기화
void pre_set()
{
	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++)
		{
			visited[i][j] = 0;
			discoverd[i][j] = 0;
			depth[i][j] = 0;
		}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp;
	int are_number = 2;
	int result = 987654321;

	cin >> n;

	pre_set();

	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> temp;
			board[i][j] = temp;
		}

	//같은 대륙을 같은 숫자(2부터)로 체크한다
	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++)
		{
			if (board[i][j] == 1)
			{
				numberCheck(make_pair(i, j), are_number);
				are_number++;
			}
		}

	//2번 대륙부터 bfs를 통해 다른 대륙과 이어지는 가장 짧은 거리를 찾는다
	//그중 가장 짧은 거리를 찾는다
	for (int i = 2; i < are_number; i++)
	{
		pre_set();
		result = min(result, Solve(end_point_list[i], i));
	}

	cout << result;
	
	return 0;
}