백준 2146번 다리 만들기

1. 2146번 다리 만들기
    1-1. 링크
    1-2. 문제 해석
    1-3. 코드 및 해설

 

 

 

---

 

1. 2146번 다리 만들기

1-1. 링크

2146번: 다리 만들기

 

1-2. 문제 해석

예시

 

섬에서 섬을 잇는 다리를 1개 놓는다고 했을 때 가장 짧은 다리의 길이를 구하는 문제이다.

위 예시에서 색칠된 부분이 섬이고 색칠되지 않은 부분이 바다라고 보면 된다.

 

깃발이 있는 위치를 다리로 이어보자

 

위 예시에서는 깃발 사이에 다리를 건설했을 때 가장 짧은 길이의 다리를 만들 수 있다.

 

어쩌다보니 하트 모양이 됐네...♡

 

위 사진은 위쪽 깃발 위치를 기준으로 다리를 건설했을 때 길이가 얼마나 드는지를 보여주고 있다.

그리고 이 길이는 BFS를 이용하면 구할 수 있다.

즉, 섬에서 출발해서 다른 섬에 도달할 때까지의 거리를 BFS로 구하면 된다는 것이다.

 

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로 표현한다는 것이다.

BFS를 돌다가 다른 섬에 도달하면 다리의 길이를 업데이트해야 하는데

이게 내 섬의 다른 좌표인지... 다른 섬의 좌표인지... 알 수가 없다는 것이다.

그래서 가장 먼저 해야 할 것은 각각의 섬을 각각 다른 숫자 값으로 바꿔주는 작업이다.

 

2 2 2 0 0 0 0 3 3 3
2 2 2 2 0 0 0 0 3 3
2 0 2 2 0 0 0 0 3 3
0 0 2 2 2 0 0 0 0 3
0 0 0 2 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0
0 0 0 0 4 4 0 0 0 0
0 0 0 0 4 4 4 0 0 0
0 0 0 0 0 0 0 0 0 0

바로 이런 식으로 말이다.

DFS나 BFS를 사용하면 된다.

 

그다음에는 모든 좌표값을 돌면서 BFS로 가장 짧은 다리의 길이를 최신화해주면 된다.

방문 여부를 잘 확인해서 시간 초과가 나지 않게 유의해야 하고, 나는 가지치기를 해서 시간을 단축했다.

 

1-3. 코드 및 해설

public class _2146_다리_만들기 {
	static int[][] map;
	static boolean[][] visited;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int N, min = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];

		// 입력
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int cnt = 2; // 섬에 번호를 매긴다. (2부터 시작)
		visited = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1) { // 1이면 아직 번호를 매기지 않은 섬
					map[i][j] = cnt;
					visited[i][j] = true;
					DFS(i, j, cnt++); // DFS를 이용해 번호를 매겨준다.
				}

				if (map[i][j] != 0) { // 현재 위치가 섬이라면
					BFS(i, j); // BFS를 이용해서 다른 섬까지 도달하는데 필요한 다리의 길이를 구한다.
				}
			}
		}

		System.out.println(min);
	}

	public static void DFS(int y, int x, int cnt) {
		for (int i = 0; i < 4; i++) {
			int newY = y + dy[i];
			int newX = x + dx[i];

			if (isMovable(newY, newX) && !visited[newY][newX] && map[newY][newX] == 1) {
				visited[newY][newX] = true;
				map[newY][newX] = cnt; // 섬에 번호를 매겨준다.
				DFS(newY, newX, cnt);
			}
		}
	}

	public static void BFS(int y, int x) {
		Queue<Pos> queue = new LinkedList<>();
		queue.add(new Pos(y, x, 0));
		boolean[][] visited = new boolean[N][N];
		visited[y][x] = true;

		while (!queue.isEmpty()) {
			Pos p = queue.poll();

			// 가지치기. 다리의 길이가 이전에 구한 가장 짧은 다리의 길이보다 구하면 더이상 조사할 필요가없다.
			if (p.dist >= min) {
				return;
			}

			for (int i = 0; i < 4; i++) {
				int newY = p.y + dy[i];
				int newX = p.x + dx[i];

				if (isMovable(newY, newX) && !visited[newY][newX]) {
					if (map[newY][newX] == 0) { // 바다라면
						visited[newY][newX] = true;
						queue.add(new Pos(newY, newX, p.dist + 1)); // 다리 길이 + 1
					}

					else if (map[newY][newX] != map[y][x]) { // 다른 섬에 도달했다면
						min = Math.min(min, p.dist); // 다리 길이를 비교해서 작은 값을 저장한다.
					}
				}
			}
		}
	}

	public static boolean isMovable(int y, int x) {
		if (y < 0 || x < 0 || y >= N || x >= N) {
			return false;
		}

		return true;
	}

	static class Pos {
		int y;
		int x;
		int dist;

		public Pos(int y, int x, int dist) {
			this.y = y;
			this.x = x;
			this.dist = dist;
		}
	}
}

우선... 번호를 매기는 알고리즘은 DFS나 BFS를 사용하면 된다.

어차피 섬의 모든 좌표를 방문해야 하므로 속도는 같기 때문에 뭐를 사용하든 상관없는데

BFS가 2개면 네이밍도 겹치고 Pos의 dist값이 필요 없기도 하고 등등의 이유로 DFS를 사용했다.

 

2. 실행 결과

가지치기 여부에 따른 실행결과

 

가지치기의 중요성을 깨달을 수 있는 실행결과였다.

 

3. 문제 풀면서 한 실수

3-1. BFS 메모리 초과

(0, 0)을 조사한다고 해보자

 

사실 내가 처음 생각했던 방법은 비슷하지만 좀 달랐다.

예를 들어 (0, 0)을 조사한다고 해보자

 

다리 길이 정보

 

(0, 0)에서 시작해 BFS를 도는데 섬 내부라면 +1을 하지 않고

바다를 만나면 +1을 하고

다른 섬을 만나면 그때의 거리 값으로 최단 거리를 업데이트했다.

이렇게 하면 이 섬에서 가장 가까운 섬과의 거리를 다 구해본 것이므로

포문을 돌 때 이 섬이 나오면 BFS를 실행하지 않는다.

(HashSet으로 검사 여부를 처리해줬다)

 

음...

여러 테스트 케이스를 넣어봤고 정답도 잘 나왔지만 메모리 초과가 났다.

나중에 알게 된 거지만 풀이 자체가 잘못됐다기보단 BFS를 사용할 때 흔히 실수하기 쉬운 점을 내가 간과했다.

 

 

21억으로 거리를 초기화 해놓고 (0, 0)부터 거리를 업데이트 해나가는 과정

 

• 첫 번째 그림: 21억으로 전부 초기화한 상태
• 두 번째 그림: (0, 0)을 시작점으로 잡고 거리를 0으로 설정한 상태
• 세 번째 그림: 한 칸 이동하고 거리를 업데이트한 상태

초록색이 섬이고 파란색이 바다라고 쳤을 때

모든 좌표의 거리를 21억으로 초기화해놓고

(0, 0)부터 BFS를 돌며 거리를 업데이트해나간다고 해보자

 

→ 방향으로 먼저 들렀다가 ↓방향을 들르는 경우

 

↓방향으로 먼저 들렀다가 → 방향을 들르는 경우

 

(0, 1)과 (1, 0)에서 (1, 1)로 간다고 했을 때 순서에 따른 결과는 위와 같다.

네 번째 사진에서 (1, 0)에서 (1, 1)로 갈 때

(1, 1)이 1이 아니라 0인 이유는 이동할 좌표가 가지고 있는 distance값이 더 작기 때문이다.

그래서 나는 이걸 if문 처리해주면 아무 문제없이 풀릴 거라 생각했다.

하지만 현실은 메모리 초과.

이유는 무엇일까?

 

↓방향으로 먼저 들렀다가 → 방향을 들르는 경우

 

그 이유는 Queue에 쌓이는 데이터에 있다.

만약 위와 같은 순서로 BFS 탐색을 하게 된다면 아무런 문제가 없다.

↓ 방향으로 탐색하고 Queue에 값을 넣은 다음

→ 방향으로 탐색할 때는 if문에 걸러져서 Queue에 값이 들어가지 않을 테니까

 

→ 방향으로 먼저 들렀다가 ↓방향을 들르는 경우

 

문제는 바로 이런 경우이다.

→ 방향을 먼저 탐색하니 Queue에 값이 들어가고

↓ 방향으로 탐색할 때 if문에 걸러지지 않아서 또 Queue에 값이 들어간다.

즉, 좌표 (1, 1)에 해당하는 값이 Queue에 중복해서 들어가는 것이다.

 

예시로 든 건 2x2 맵이었지만 이게 훨씬 더 큰 맵이라면?

중복해서 들어간 Queue의 값이 또 다른 좌표에서 중복해서 들어가고 중복 중복 중복 중복하다 보면

2... 4... 8... 16... 32... Queue에 중복된 값이 여러 번 쌓이면서 결국 메모리 초과가 나는 것이다.

 

나는 여태까지 간단한 BFS문제만을 풀어봤기 때문에 이점을 몰랐다.

단순히 visited로 방문처리를 판단하는 게 아니라 거리에 따라서 처리를 해주려고 한다면

이 점을 주의해야 할 것 같다.

 

3-2. 또 메모리 초과

[목차 3-1]의 이유 말고도 여러 번 메모리 초과가 났었는데

섬의 종류를 구분할 때 써야 할 visited와 거리를 구할때 써야할 visited를 잘못 혼용해서 사용한다든지

방문 처리할 때 이동할 좌표가 아니라 다른 좌표값을 준다든지 등등의 실수가 있었다.

하지만 공통적으로 다 visited와 관련된 실수였고

BFS문제를 풀 때 메모리 초과가 난다면 방문 처리하는 로직을 가장 먼저 살펴봐야 한다는 것을 배웠다.

 

---

💡 느낀 점

• BFS는 이제 자유롭게 활용해서 쓸 수 있을 거라 생각했는데 아직 멀었구나...
• 메모리 초과 = 방문처리 로직 = visited 의심해보기!!! 메모!!!
• 방문처리 대신 거리로 이동할지 말지 여부를 정하는 건 생각보다 깊게 고민해봐야 할 로직인 것 같다. 애초에 이게 가능하긴 한 걸까? visited로 풀 수 있으면 최대한 visited를 사용하자.

---