2146 다리 만들기

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

2146번: 다리 만들기

다리 만들기 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

192 MB

14379

4991

3155

32.786%

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

 

출처

• 빠진 조건을 찾은 사람: choiking10
• 데이터를 추가한 사람: hello70825
• 잘못된 데이터를 찾은 사람: tncks0121

 

<개인 풀이>

1.DFS로 땅들의 위치를 찾고 연결요소(섬 번호)를 만든다.

 

2. 땅 좌표들을 모두 queue에 담는다. 
  -> 섬의 사이드 부분 (윤곽선) (모서리) 해당 하는 좌표들로 부터 
      다른 번호를 가진 섬까지의 최단거리를 모두 검색

 

3. 각 땅들의 좌표들로부터 얻어진 최단 거리들중 가장 최소값을 출력.

 

#include<stdio.h>
#include<queue>
#include<cstring>
using namespace std;

int mat[100][100];
int distance_[100][100];
bool check[100][100];

void dfs(int x,int y, int component);

void bfs(int x, int y, int component,int dist);
int n;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int ans = 10001;
int main(void)
{
	scanf("%d", &n);

	for (unsigned short i = 0; i < n; ++i)
	{
		for (unsigned short k = 0; k < n;++k)
			scanf("%d", &mat[i][k]);
	}

	int component = 0;
	for (unsigned short i = 0; i < n; ++i)
	{
		for (unsigned short k = 0; k < n; ++k)
		{
			if (check[i][k] == false && mat[i][k]!=0)
			{
				component += 1;
				dfs(i, k, component);
			}
		}
	} //연결 요소.

	component = 0;
	int k = 0;
	queue<pair<int, int>> land;

	//섬의 좌표들을 넣어놓고
	for (unsigned short i = 0; i < n; ++i)
	{
		for (unsigned short k = 0; k < n; ++k)
		{
			if (mat[i][k] != 0)
				land.push(make_pair(i, k));
		}
	}

	int q_size = land.size();
	//각 섬들의 좌표를 빼가며 최단거리 검색
	for (unsigned short i = 0; i < q_size; ++i)
	{
		memset(check, 0, sizeof(check));
		memset(distance_, 0, sizeof(distance_));
		int x = land.front().first;
		int y = land.front().second;
		if (x == 3 && y == 4)
			int a = 0;
		land.pop();
		int component = mat[x][y];
		bfs(x, y, component, 0);
	}

	printf("%d\n", ans);
	return 0;
}

void dfs(int x, int y, int component)
{
	check[x][y] = true;
	mat[x][y] = component;

	for (unsigned short i = 0; i < 4; ++i)
	{
		int xn = x + dx[i];
		int yn = y + dy[i];

		if (xn >= 0 && xn < n && yn >= 0 && yn < n &&
			mat[xn][yn] != 0 && check[xn][yn] == 0)
		{
			dfs(xn, yn, component);
		}
		
	}
}
void bfs(int x, int y, int component,int dist)
{
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));

	distance_[x][y] = dist;
	check[x][y] = true;

	while (!q.empty())
	{
		int xp, yp;
		xp = q.front().first;
		yp = q.front().second;
		q.pop();
		for (unsigned short i = 0; i < 4; ++i)
		{
			int xn = xp + dx[i];
			int yn = yp + dy[i];

			if (xn >= 0 && xn < n && yn >= 0 && yn < n &&
				component != mat[xn][yn] && mat[xn][yn] != 0)
			{
				if (distance_[xp][yp] < ans)
					ans = distance_[xp][yp];
				return;
			}

			if (xn >= 0 && xn < n && yn >= 0 && yn < n &&
				check[xn][yn] == 0 && mat[xn][yn] == 0)
			{
				check[xn][yn] = true;
				distance_[xn][yn] = distance_[xp][yp] + 1;
				q.push(make_pair(xn, yn));
			}
		}
	}
	
}