백준 2146 : 다리만들기 C++

www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

 

풀이

1. 섬들 다 label링

 -> 입력받을때 -1로 변환시키고  1부터 순서대로 label링 하면 편하드라

 

2.  각 섬별로 다른 섬에 지을 수 있는 다리 길이 중 최소값들 구하고 answer랑 비교

 -> 처음에 섬 좌표 몽땅 queue에 집어놓고, queue 크기로 조절하면서  한단계씩 BFS!!

 -> 섬과 섬 사이가 n칸 떨어져 있으며 길이 n-1짜리 다리 놓으면 됨!!! (이거 때문에 헷갈려서 고생했으요)

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

int map[100][100];
int visited[100][100];
int n;
int answer = 987654321;

int d_r[4] = { 0,0,1,-1 };
int d_c[4] = { 1,-1,0,0 };

void dfs(int r, int c, int index)
{
	map[r][c] = index;

	for (int i = 0; i < 4; i++)
	{
		int new_r = r + d_r[i];
		int new_c = c + d_c[i];

		if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= n)
			continue;
		if (map[new_r][new_c] == -1)
			dfs(new_r, new_c, index);
	}
}

void bfs(int index)
{
	
	queue<pair<int, int> > q;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == index)
			{
				q.push(make_pair(i, j));
				visited[i][j] = 1;
			}//모든 섬의 좌표 다 삽입
		}

	int result = 0;// 한칸 떨어져 있으면 다리길이 0임

	while (!q.empty())
	{
		int a = q.size();
		for (int i = 0; i < a; i++)//단계별!!, 거리별
		{
			int r = q.front().first;
			int c = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++)
			{
				int new_r = r + d_r[i];
				int new_c = c + d_c[i];

				if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= n)//지도 밖으로
					continue;
				if (map[new_r][new_c] != 0 && map[new_r][new_c] != index)//다른 섬 도착!! 
				{
					answer = min(answer, result);
					return;
				}
				if (map[new_r][new_c] == 0 && visited[new_r][new_c] == 0)//바다고, 방문한적 X
				{
					visited[new_r][new_c] = 1;//방문 처리
					q.push(make_pair(new_r, new_c));
				}

			}
		}
		result++;
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 1)
				map[i][j] = -1;
		}
	int index = 1;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == -1)//라벨링 안된 섬
			{
				dfs(i, j, index);
				index++;
			}
		}

	for (int i = 1; i < index; i++)
	{
		memset(visited, 0, sizeof(visited));
		bfs(i);//i번쨰 섬에서 지을수 있는 최소 길이 다리!
	}

	cout << answer << endl;
	return 0;
}