문제 출처

1. 문제설명

  • NxN 크기의 맵이 주어진다.
  • 각 칸은 1 또는 0으로 구성된다.
    • 1은 섬, 0은 바다이다.
  • 맵은 여러 개의 섬으로 구성되어 있다.
  • 여기서 다리를 놓아 두 섬을 연결하고자 한다.
    • 단, 가장 짧은 다리를 놓으려고 한다.
  • 가장 짧은 다리의 길이를 구하라!



2. 알고리즘 설계

  • 예를들어, 섬이 3개가 있다고 가정해보자.

    1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

  • 각 섬을, 1, 2, 3번으로 구성한다.

    1 1 1 0 0 0 0 2 2 2
1 1 1 1 0 0 0 0 2 2
1 0 1 1 0 0 0 0 2 2
0 0 1 1 1 0 0 0 0 2
0 0 0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 3 3 0 0 0 0
0 0 0 0 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0
  • 각 섬에서 바다와 가장 인접한 칸부터 다른 섬을 만날 때까지 찾는다.
    • for-loop로 (0,0)부터 시작하면 가장 처음 걸리는 칸은 (0,3)이 된다.
    • 다른 섬과 가장 빠른 길(x로 표시)을 찾으면 4칸이다.
    1 1 1 x x x x 2 2 2
1 1 1 1 0 0 0 0 2 2
1 0 1 1 0 0 0 0 2 2
0 0 1 1 1 0 0 0 0 2
0 0 0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 3 3 0 0 0 0
0 0 0 0 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0
  • 위와 같은 식으로 모든 경로의 길이를 구한다.
  • 가장 짧은 길이를 출력하면 된다.



3. 로직

  • 각 섬에 번호를 매기는 방법은 두가지가 있다.
    • bfs로 현재 1부터 0이 아닌 부분 전부 번호 매기기
    • dfs로 현재 1부터 0이 아닌 부분 전부 번호 매기기
  • 섬과 섬 간의 최단 거리는 BFS로 구해주었다.
    • 상하좌우 한 칸씩 탐색을 하면서, 움직여 주면 된다.
  • 주의할 점
    • 섬과 섬 간의 거리를 구할 때, 방문 표시하는 배열과
    • 처음 탐색 시작 위치를 방문 표시하는 배열을
    • 별도로 두어야 한다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

typedef struct {
	int y, x, dist;
}Pos;

const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
const int SZ = 100, INF = 0x3f3f3f;
int n, ans = INF, division = 1;
pii arr[SZ][SZ];
bool visited[SZ][SZ];
bool tmp[SZ][SZ];

void get_division(int sy, int sx) {
	queue<pii> q;
	q.push({ sy, sx });
	visited[sy][sx] = true;
	arr[sy][sx].second = division;

	while (!q.empty()) {
		pii cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.first + dy[dir];
			int nx = cur.second + dx[dir];

			if (ny < 0 || nx < 0 || ny >= n || nx >= n)
				continue;
			if (!visited[ny][nx] && arr[ny][nx].first == 1) {
				arr[ny][nx].second = division;
				q.push({ ny,nx });
				visited[ny][nx] = true;
			}
		}
	}
}

int get_distance(pii src, int cur_division) {
	fill_n(&visited[0][0], SZ * SZ, false);

	queue<Pos> q;
	q.push({ src.first, src.second, 1 });
	visited[src.first][src.second] = true;

	while (!q.empty()) {
		Pos cur = q.front();
		q.pop();

		if (arr[cur.y][cur.x].first == 1 && arr[cur.y][cur.x].second != cur_division)
			return cur.dist - 1;

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.y + dy[dir];
			int nx = cur.x + dx[dir];

			if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
			if (arr[ny][nx].second != cur_division && !visited[ny][nx]) {
				q.push({ ny,nx, cur.dist + 1 });
				visited[ny][nx] = true;
			}
		}
	}

	return INF;
}

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

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j].first;
			arr[i][j].second = 0;
		}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j].first == 1 && !visited[i][j]) {
				get_division(i, j);
				division++;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j].first == 1) {
				for (int dir = 0; dir < 4; dir++) {
					int ny = i + dy[dir];
					int nx = j + dx[dir];

					if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
					if (arr[ny][nx].first == 0 && !tmp[ny][nx]) {
						int dist = get_distance({ ny,nx }, arr[i][j].second);
						tmp[ny][nx] = true;

						ans = min(ans, dist);
					}
				}
			}
		}
	}

	cout << ans;
	return 0;
}



5. 기타

  • 처음 get_distance()에서 정답을 찾았을 때 외엔 반환을 하지 않았다.
  • 그러나 다음 경우를 간과했다.
    • 다른 섬으로 갈 수 없는 경우였다.
    1 1 1
1 0 1
1 1 1
  • 위 예시는 내 로직에 의하면 (1,1)에서 다른 섬으로 갈 수 있는지 시도한다.
  • 그러나 다른 섬에 도착할 수가 없다.
  • 그래서 시도하다가 큐가 비어버리고 처음 while-loop를 탈출하게 된다.
    • 그러나 return 값이 없다.
  • 그래서 이미지와 같은 런타임 에러가 발생했다.
    • 이 에러는 발생 원인이 여러가지가 있지만,
    • 대표적인 것 중 하나로 main()을 제외한 반환값이 있는 함수가 반환을 하지 않았을 때 라고 한다.