[백준] 2146. 다리 만들기

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

2146번: 다리 만들기

이 문제의 핵심은, 섬들의 가장자리에서 bfs로 바다를 탐색하면 된다. 그러다가 다른 섬을 만났을 때 이동한 카운트가 가장 작은 것이 정답이다. 

 

이렇게 푸는데 있어서 흐름은 다음과 같다.

1. 우선 각 섬들을 bfs해서 각 섬들에 번호를 매겨주어야 한다(2, 3, 4, ...). 이는 나중에 바다를 탐색하다가 섬에 닿았을 때 시작 섬과 도착 섬이 같은 섬인지 아닌지를 구분하기 위함이다.
2. 또 한번 각 섬들을 bfs해서 각 섬들의 가장자리를 찾아낸다. 
   1. 가장 자리를 찾았으면 바다로 bfs한다.
   2. 바다를 bfs하는 도중에 섬을 만났으면, 
      1. 시작 섬과 같은 섬이면 pass하고,
      2. 시작 섬과 다른 섬이면 그 이동 거리를 정답 값으로 갱신할지말지 결정한다.

그리고 주의할 점은 다음과 같다.

• 1번을 수행한 후 visited 배열을 false로 초기화해야 한다. 그리고 2번을 수행해야 한다.
• 2-1번에서 바다를 탐색할 때는 각 탐색마다 seaVisited 배열이 매번 새로 생성되어야 한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n][n];

        // 0. map 초기화
        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());
            }
        }

        // 1. 각각의 섬을 탐색하면서 섬 번호를 매겨주기(2, 3, ...) (나중에 바다 탐색할 때 시작 섬과 도착 섬이 같은지 다른지 확인하기 위함)
        int num = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 0 && !visited[i][j]) {
                    bfs(i, j, num++);
                }
            }
        }

        for (boolean[] arr : visited) {
            Arrays.fill(arr, false);
        }

        // 2. 다시 각각의 섬을 탐색하다가 가장자리이면, 바다 탐색하기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 0 && !visited[i][j]) {
                    bfs(i, j);
                }
            }
        }

        System.out.println(answer);
    }

    public static void bfs(int y, int x, int num) {
        Queue<Node> que = new LinkedList<>();
        visited[y][x] = true;
        map[y][x] = num; // 번호 매겨주기
        que.add(new Node(y, x));

        while (!que.isEmpty()) {
            Node now = que.poll();

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (visited[ny][nx]) continue;

                // 다음 노드가 섬이면 계속 진행
                if (map[ny][nx] == 1) {
                    visited[ny][nx] = true;
                    map[ny][nx] = num; // 번호 매겨주기
                    que.add(new Node(ny, nx));
                }
            }
        }
    }

    public static void bfs(int y, int x) {
        Queue<Node> que = new LinkedList<>();
        visited[y][x] = true;
        que.add(new Node(y, x));

        while (!que.isEmpty()) {
            Node now = que.poll();

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (visited[ny][nx]) continue;

                // 다음 노드가 섬이면 계속 진행
                if (map[ny][nx] == 1) {
                    visited[ny][nx] = true;
                    que.add(new Node(ny, nx));
                }

                // 다음 노드가 바다이면 바다 탐색 시작
                if (map[ny][nx] == 0) {
                    seaBfs(ny, nx, map[now.y][now.x]);
                }
            }
        }
    }

    public static void seaBfs(int y, int x, int startNum) {
        Queue<Node> que = new LinkedList<>();
        int[][] seaVisited = new int[n][n]; // 바다를 탐색할 때마다 매번 방문처리 배열은 새로 생성되어야 함
        seaVisited[y][x] = 1;
        que.add(new Node(y, x));

        while (!que.isEmpty()) {
            Node now = que.poll();

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (seaVisited[ny][nx] != 0) continue;

                // 다음 노드가 섬이면
                if (map[ny][nx] != 0) {
                    // 같은 섬이면 패스
                    if (map[ny][nx] == startNum) {
                        continue;
                    }
                    // 다른 섬이면 정답 갱신
                    else {
                        answer = Math.min(answer, seaVisited[now.y][now.x]);
                        return;
                    }
                }

                // 다음 노드가 바다이면 계속 진행
                if (map[ny][nx] == 0) {
                    seaVisited[ny][nx] = seaVisited[now.y][now.x] + 1;
                    que.add(new Node(ny, nx));
                }
            }
        }
    }

    public static class Node {
        int y, x;

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

 

매번 알고리즘 문제 푸는 게 숙제처럼 느껴져서 대충 풀고 안되면 답 보고 그랬는데, 이번 문제는 진짜 혼자 힘으로 끝까지 고민해서 풀었다! 앞으로도 이렇게 하자..!