BOJ 17472 : 다리 만들기 2 (A형 상시)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

 

www.acmicpc.net/problem/17472

 

이후 설명 및 입/출력은 링크 참고

 

아래의 순서대로 구현한다.

 

1) BFS를 이용해 섬을 구분한다.

2) 섬과 섬 사이의 거리를 구한다.

3) 섬의 개수 N에 대해, 다리 N - 1개를 선택하여 모두 연결되어 있다면, 다리의 길이를 갱신한다.

---

구조체는 좌표를 기억하기 위한 RC 구조체가 필요하다.

MAP 주변은 모두 -1로 처리하고 (1, 1)부터 입력을 받는다.

connect 배열은 섬과 섬 사이의 거리를 저장하기 위한 배열이다.

섬과 섬 사이의 거리는 가장 가까운 거리만 필요하므로, 큰 값(WORST = 0x7fff0000)으로 초기화한다.

islandList는 각 섬의 좌표를 입력받기 위한 RC 배열이다.

#define MAX (10 + 5)
#define WORST (0x7fff0000)

int N, M, ISLAND_COUNT;
int MAP[MAX][MAX];
int visit[MAX][MAX];
int connect[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}RC;

RC queue[MAX * MAX];
int wp, rp;

RC islandList[6 + 5][MAX * MAX];
int icnt[6 + 5];

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= M + 1; c++)
			MAP[r][c] = -1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);

	for (int r = 1; r <= 6; r++)
		for (int c = 1; c <= 6; c++)
			connect[r][c] = WORST;
}

---

1) BFS를 이용해 섬을 구분한다.

 

입력된 MAP에 섬은 1로 표시되어 있다. 

따라서 섬의 개수를 세면서 섬의 번호를 표시할 필요가 있다.

이것은 BOJ 2667 : 단지번호붙이기에서 사용한 BFS를 이용하여 나눌 수 있다.

MAP에서 (r, c)가 1이 있는 경우, 그리고 방문하지 않은 경우 BFS를 이용하여 MAP을 표시한다.

ISLAND_COUNT = 1;
for (int r = 1; r <= N; r++)
	for (int c = 1; c <= M; c++)
		if (MAP[r][c] == 1 && visit[r][c] == 0) BFS(r, c, ISLAND_COUNT++);

 

output()을 이용해 출력해보면, 예제의 번호와는 다르게 번호가 매겨진다. (output은 최종 코드 참고)

row가 낮은 것부터 BFS를 실행했기 때문에 순서가 바뀔 수는 있지만, 다리의 최소 길이를 구하는 데 문제는 없다.

island 번호를 넘겨 받은 BFS는 visit을 참고하여, MAP의 주변이 1인 경우 island로 MAP을 변경한다.

주변의 탐색은 dr, dc 배열을 이용하고, 벽인 경우는 무시한다.

처음에 1을 받기 때문에 최초의 섬은 변경사항은 없고, visit에 체크만 하게 된다.

그리고 섬과 섬 사이의 거리를 구하기 위해 islandList에 각 섬에 해당하는 좌표를 추가한다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS(int r, int c, int island)
{
	wp = rp = 0;

	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = 1;
	MAP[r][c] = island;

	int& index = icnt[island];
	/* distance를 구하기 위한 좌표 추가 */
	islandList[island][index].r = r;
	islandList[island][index++].c = c;

	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (MAP[nr][nc] == -1) continue;

			if (visit[nr][nc] == 0 && MAP[nr][nc] != 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;
				MAP[nr][nc] = island;

				/* distance를 구하기 위한 좌표 추가 */
				islandList[island][index].r = nr;
				islandList[island][index++].c = nc;
			}
		}
	}
}

---

2) 섬과 섬 사이의 거리를 구한다.

 

1번 섬부터 주변의 섬을 탐색하는 getDistance를 호출한다.

for (int i = 1; i < ISLAND_COUNT; i++) getDistance(i);

 

MAP에 섬의 번호를 매겼고, islandList에 각 섬의 좌표를 저장하였으므로, 각 섬의 거리를 구한다.

섬의 거리는 connect 배열에 저장한다.

섬 1과 섬 2의 거리는 connect[1][2] = connect[2][1]이 된다.

섬의 개수가 작기 때문에 섬 1과 2의 거리를 찾더라도, 2에서 1을 찾지 않게 할 필요는 없다.

 

icnt에는 각 island의 좌표의 수가 저장되어있으므로, 참조자를 이용해 index로 이름을 변경한다.

그리고 좌표를 기준으로 4방향을 끝까지 가본다.

이 때, 한 방향에 끝까지 가본 후, 다음 방향을 탐색하도록 한다.

 

distance를 1부터 증가하면서 벽(-1)이나 자기 자신(isalnd)의 번호가 나오면 break로 종료한다.

그 외의 숫자가 나오면 다른 섬이기 때문에 connectIsland 변수에 저장하고, 거리를 갱신한다.

 

distance는 MAP[nr][nc]가 다른 섬일 때 까지 증가하였으므로, 실제 거리는 1을 빼야한다.

그리고 문제에서 다리의 길이가 2 이상이어야 한다고 하였으므로, 1이하인 경우는 무시한다.

마지막으로 connect 배열에 더 작은 다리의 길이로 갱신하면 된다.

(connect 배열은 최초에 최악의 값(0x7fff0000)이 들어있다.)

void getDistance(int island)
{
	int& index = icnt[island];

	for (int i = 0; i < index; i++)
	{
		int sr, sc;

		sr = islandList[island][i].r;
		sc = islandList[island][i].c;

		for (int dir = 0; dir < 4; dir++)
		{
			int distance, connectIsland;

			connectIsland = 0;
			for (distance = 1; ; distance++)
			{
				int nr, nc;

				nr = sr + dr[dir] * distance;
				nc = sc + dc[dir] * distance;

				if (MAP[nr][nc] == -1 || MAP[nr][nc] == island) break;
				if (MAP[nr][nc] != 0)
				{
					connectIsland = MAP[nr][nc];
					break;
				}
			}

			distance--; /* MAP[nr][nc]가 island이 경우 종료하므로 1을 빼야 한다. */
			if (distance <= 1) continue; /* 다리의 길이가 1 이하인 경우는 무시 */

			/* 최솟값 갱신 */
			if (distance < connect[island][connectIsland] && connectIsland != 0)
			{
				connect[island][connectIsland] = distance;
				connect[connectIsland][island] = distance;
			}
		}
	}
}

만약 2번 섬과 3번 섬이 연결될 수 없다면 connect[2][3] = connect[3][2] = WORST로 남아있게 된다.

이것은 나중에 다리를 선택할 때, 연결되지 않은 다리로 선택을 피할 수 있는 조건이 된다.

---

3) 섬의 개수 N에 대해, 다리 N - 1개를 선택하여 모두 연결되어 있다면, 다리의 길이를 갱신한다.

 

예제의 섬의 개수는 총 4개이다. 

그렇다면 최소의 다리의 수는 3이 된다. 

하지만 1 - 2, 2 - 3, 3 - 1의 다리를 선택하게 되면 4는 연결되지 않으므로, 

만들 수 있는 다리를 N - 1개 선택한 후, 모두 연결되어있는지 다시 체크해야 한다.

 

먼저 DFS를 이용해 N - 1개의 다리를 선택한다.

다리의 선택은 connect 배열에 WORST(0x7fff0000)가 아닌 경우 선택할 수 있다.

하지만 connect[N][M] = connect[M][N]이기 때문에, 중복해서 선택할 필요가 없다.

따라서 대각선을 기준으로 아래는 지운다.

for (int r = 1; r < ISLAND_COUNT; r++)
	for (int c = 1; c <= r; c++)
		connect[r][c] = 0;

 

위의 코드를 실행하면 outputConnect() 함수로 connect가 지워진 것을 확인할 수 있다.

(outputConnect는 최종 코드 참고)

DFS는 아래와 같이 구현한다.

 

selectVisit 배열 : 선택된 다리, select[2][3] = 1이라면 2번 섬과 3번 섬이 연결된 다리를 선택한 경우다.

 

1) DFS 종료 조건은 L = ISLAND_COUNT - 1, 즉, 섬의 개수 - 1 개일 때 종료한다.

2) DFS 종료 조건에서 모든 섬이 연결된 것은 BFS와 selectVisit으로 확인한다.

3) L이 ISLAND_COUNT - 1이 아니라면 섬을 선택한다.

   선택된 섬의 번호 2개를 select 배열에 증가하고, selectVisit에도 표시한다.

   DFS 종료 후에는 원래대로 돌려준다.

4) DFS로 넘어가면서 다리의 길이를 증가한다.

 

3) 에서 selectVisit[r][c]가 1인 경우는 r 섬과 c 섬이 연결된 다리를 선택한 경우이므로 무시하고,

connect[r][c]가 0인 경우는 위에서 필요없는 경우로 지웠으므로 무시한다.

connect[r][c]가 WORST인 경우는 연결될 수 없는 다리이므로 무시한다.

int MINANS = 0x7fff0000;
int selectVisit[MAX][MAX];

void DFS(int L, int sr, int sc, int length)
{
	if (L == ISLAND_COUNT - 1)
	{
		if (checkAllBridge() == 0) return;

		if (length < MINANS) MINANS = length;

		return;
	}

	for (int r = sr; r < ISLAND_COUNT; r++)
	{
		for (int c = r + 1; c < ISLAND_COUNT; c++)
		{
			if (selectVisit[r][c] || connect[r][c] == 0 || connect[r][c] == WORST) continue;

			selectVisit[r][c] = 1;
			selectVisit[c][r] = 1;


			DFS(L + 1, r, c, length + connect[r][c]);

			selectVisit[r][c] = 0;
			selectVisit[c][r] = 0;

		}
	}
}

 

checkAllBridge는 selectVisit을 보고 1번 섬과 연결된 섬을 BFS 탐색으로 찾는다.

 

i == out → 자기 자신이 아니고,

visit[i] → 아직 방문하지 않았고,

selectVisit[out][i] → 연결되지 않은 경우는 continue 처리하고,

 

그렇지 않은 경우는 queue에 담으면서 탐색한다.

최종적으로 write pointer = wp가 (섬의 개수 - 1)과 같으면 모든 섬이 연결되었다고 볼 수 있다.

int selectVisit[MAX][MAX];

int checkAllBridge()
{
	int queue[10] = { 0 };
	int visit[10] = { 0 };

	wp = rp = 0;

	queue[wp++] = 1;
	visit[1] = 1;

	while (wp > rp)
	{
		int out = queue[rp++];

		for (int i = 1; i < ISLAND_COUNT; i++)
		{
			if (i == out || visit[i] || selectVisit[out][i] == 0) continue;

			queue[wp++] = i;
			visit[i] = 1;
		}
	}

	return (wp == ISLAND_COUNT - 1);
}

checkAllBridge가 1을 return하면 다리의 길이 length를 MINANS와 비교하여 갱신하면 된다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (10 + 5)
#define WORST (0x7fff0000)

int N, M, ISLAND_COUNT;
int MAP[MAX][MAX];
int visit[MAX][MAX];
int connect[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}RC;

RC queue[MAX*MAX];
int wp, rp;

RC islandList[6 + 5][MAX * MAX];
int icnt[6 + 5];

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= M + 1; c++)
			MAP[r][c] = -1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);

	for (int r = 1; r <= 6; r++)
		for (int c = 1; c <= 6; c++)
			connect[r][c] = WORST;
}

void output()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void outputConnect()
{
	printf("  %d %d %d %d %d %d\n", 1, 2, 3, 4, 5, 6);
	for (int r = 1; r <= 6; r++)
	{
		printf("%d ", r);
		for (int c = 1; c <= 6; c++)
			printf("%d ", connect[r][c] == WORST ? 0 : connect[r][c]);
		putchar('\n');
	}
	putchar('\n');
}


/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS(int r, int c, int island)
{
	wp = rp = 0;

	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = 1;
	MAP[r][c] = island;

	int& index = icnt[island];
	/* distance를 구하기 위한 좌표 추가 */
	islandList[island][index].r = r;
	islandList[island][index++].c = c;

	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (MAP[nr][nc] == -1) continue;

			if (visit[nr][nc] == 0 && MAP[nr][nc] != 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;
				MAP[nr][nc] = island;

				/* distance를 구하기 위한 좌표 추가 */
				islandList[island][index].r = nr;
				islandList[island][index++].c = nc;
			}
		}
	}
}

void getDistance(int island)
{
	int& index = icnt[island];

	for (int i = 0; i < index; i++)
	{
		int sr, sc;

		sr = islandList[island][i].r;
		sc = islandList[island][i].c;

		for (int dir = 0; dir < 4; dir++)
		{
			int distance, connectIsland;

			connectIsland = 0;
			for (distance = 1; ; distance++)
			{
				int nr, nc;

				nr = sr + dr[dir] * distance;
				nc = sc + dc[dir] * distance;

				if (MAP[nr][nc] == -1 || MAP[nr][nc] == island) break;
				if (MAP[nr][nc] != 0)
				{
					connectIsland = MAP[nr][nc];
					break;
				}
			}

			distance--; /* MAP[nr][nc]가 island이 경우 종료하므로 1을 빼야 한다. */
			if (distance <= 1) continue; /* 다리의 길이가 1 이하인 경우는 무시 */

			/* 최솟값 갱신 */
			if (distance < connect[island][connectIsland] && connectIsland != 0)
			{
				connect[island][connectIsland] = distance;
				connect[connectIsland][island] = distance;
			}
		}
	}

}

int MINANS = 0x7fff0000;
int selectVisit[MAX][MAX];

int checkAllBridge()
{
	int queue[10] = { 0 };
	int visit[10] = { 0 };

	wp = rp = 0;

	queue[wp++] = 1;
	visit[1] = 1;

	while (wp > rp)
	{
		int out = queue[rp++];

		for (int i = 1; i < ISLAND_COUNT; i++)
		{
			if (i == out || visit[i] || selectVisit[out][i] == 0) continue;

			queue[wp++] = i;
			visit[i] = 1;
		}
	}

	return (wp == ISLAND_COUNT - 1);
}

void DFS(int L, int sr, int sc, int length)
{
	if (L == ISLAND_COUNT - 1)
	{
		if (checkAllBridge() == 0) return;

		if (length < MINANS) MINANS = length;

		return;
	}

	for (int r = sr; r < ISLAND_COUNT; r++)
	{
		for (int c = r + 1; c < ISLAND_COUNT; c++)
		{
			if (selectVisit[r][c] || connect[r][c] == 0 || connect[r][c] == WORST) continue;

			selectVisit[r][c] = 1;
			selectVisit[c][r] = 1;


			DFS(L + 1, r, c, length + connect[r][c]);

			selectVisit[r][c] = 0;
			selectVisit[c][r] = 0;

		}
	}
}

int main(void)
{
	input();

	ISLAND_COUNT = 1;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (MAP[r][c] == 1 && visit[r][c] == 0) BFS(r, c, ISLAND_COUNT++);

	//output();

	for (int i = 1; i < ISLAND_COUNT; i++) getDistance(i);

	for (int r = 1; r < ISLAND_COUNT; r++)
		for (int c = 1; c <= r; c++)
			connect[r][c] = 0;

	//outputConnect();

	DFS(1, 1, 1, 0);


	if (MINANS == 0x7fff0000) printf("-1\n");
	else printf("%d\n", MINANS);

	return 0;
}

---

실제 섬을 연결하는 다리의 최소 길이는 최소 스패닝 트리(MST, Minimum Spanning Tree)를 이용하면 되지만,

다리의 개수가 작아서 A형 문제 수준으로 완전 탐색을 하였다.