[2146번] 다리 만들기

- 방법①

1) 먼저, 섬을 그룹으로 나눈다. (g[i][j] = (i,j)의 그룹 번호)

2) 그 다음 각각의 그룹에 대해서 다른 섬까지 거리를 계산한다.

3) 거리 중 가장 최소값을 구한다. 

* 이 방법은 각각이 그룹에 대해서 BFS 알고리즘을 수행해야 하기 때문에 느리다. 

#include <cstdio>
#include <queue>
using namespace std;

const int MAX = 110;
int a[MAX][MAX];
int g[MAX][MAX];
int d[MAX][MAX];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0, -1,1};

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	int cnt = 0;
	queue<pair<int,int>> q;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(a[i][j] == 1 && g[i][j] == 0)
			{
				g[i][j] = ++cnt;
				q.push(make_pair(i,j));
				while(!q.empty()){
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					for(int k = 0; k < 4; k++)
					{
						int nx = x + dx[k];
						int ny = y + dy[k];
						if(nx >= 0 && nx < n && ny >= 0 && ny < n)
						{
							if(a[nx][ny] == 1 && g[nx][ny] == 0)
							{
								g[nx][ny] = cnt;
								q.push(make_pair(nx,ny));
							}
						}
					}
				}
			}
		}
	}

	int ans = -1;
	queue<pair<int,int>> q2;
	for(int l=1; l<=cnt; l++) //그룹3개, 1~3
	{
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				d[i][j] = -1; // d 초기화
				if(g[i][j] == l)
				{
					q2.push(make_pair(i,j));
					d[i][j] = 0;
				}
			}
		}

		while(!q2.empty())
		{
			int x = q2.front().first;
			int y = q2.front().second;
			q2.pop();
			for(int k = 0; k < 4; k++)
			{
				int nx = x + dx[k];
				int ny = y + dy[k];
				if(nx >= 0 && nx < n && ny >= 0 && ny < n)
				{
					if(d[nx][ny] == -1)
					{
						d[nx][ny] = d[x][y] + 1;
						q2.push(make_pair(nx, ny));
					}
				}
			}
		}
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(a[i][j] == 1 && g[i][j] != l)
				{
					if(ans == -1 || d[i][j]-1 < ans)
					{
						ans = d[i][j] - 1;
					}
				}
			}
		}
	}

	printf("%d", ans);

	return 0;
}

- 방법② : 더 빠른 알고리즘으로 땅을 확장하는 방식

 1) 먼저, 섬을 그룹으로 나눈다. (g[i][j] = (i,j)의 그룹 번호)

 2) 그룹(g[i][j])을 기준으로 땅을 확장시키는 동시에 거리를 계산한다.

 3) 각 칸과 인접한 칸의 그룹 번호가 다르면 다리를 만들 수 있으며 그 때 거리를 이용해 다리의 최솟값을 찾는다. 

#include <cstdio>
#include <queue>
using namespace std;

const int MAX = 110;
int a[MAX][MAX];
int g[MAX][MAX];
int d[MAX][MAX];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0, -1,1};

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	int cnt = 0;
	queue<pair<int,int>> q;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(a[i][j] == 1 && g[i][j] == 0)
			{
				g[i][j] = ++cnt;
				q.push(make_pair(i,j));

				while(!q.empty())
				{
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					for(int k = 0; k < 4; k++)
					{
						int nx = x + dx[k];
						int ny = y + dy[k];
						if(nx >= 0 && nx < n && ny >= 0 && ny < n)
						{
							if(a[nx][ny] == 1 && g[nx][ny] == 0)
							{
								g[nx][ny] = cnt;
								q.push(make_pair(nx, ny));
							}
						}
					}
				}
			}
		}
	}
	queue<pair<int, int>> q2;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			d[i][j] = -1;
			if(a[i][j] == 1)
			{
				q2.push(make_pair(i,j));
				d[i][j] = 0;
			}
		}
	}
	while(!q2.empty())
	{
		int x = q2.front().first;
		int y = q2.front().second;
		q2.pop();
		for(int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(nx >= 0 && nx < n && ny >= 0 && ny < n)
			{
				if(d[nx][ny] == -1)
				{
					d[nx][ny] = d[x][y] + 1;
					g[nx][ny] = g[x][y];
					q2.push(make_pair(nx, ny));
				}
			}
		}
	}
	/*
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			printf("%d ", d[i][j]);
		}
		printf("\n");
	}
	*/
	int ans = -1;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			for(int k = 0; k < 4; k++)
			{
				int x = i + dx[k];
				int y = j + dy[k];
				if(x >= 0 && x < n && y >= 0 && y < n)
				{
					if(g[i][j] != g[x][y])
					{
						if(ans == -1 || ans > d[i][j] + d[x][y])
						{
							ans = d[i][j] + d[x][y];
						}
					}
				}
			}
		}
	}
	printf("%d", ans);

	return 0;
}