[백준] 2146: 다리 만들기 - JAVA

in Algorithm on 그래프 이론

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

풀이

그래프 탐색 문제.

서로 다른 두 개의 섬을 연결하는 다리의 최솟값을 구해야 한다.

섬은 1, 바다는 0으로 주어져서 섬들을 구분하기 위한 작업을 우선 거쳤다.

섬마다 번호를 하나씩 부여하고 bfs탐색을 통해 해당 번호를 마킹했다.

그 후 섬들끼리 거리를 bfs탐색을 통해 구했다.

처음 제출에 메모리 초과가 났었다.

섬을 구분하는 함수를 구현할 때 번호가 다른 것으로 방문처리가 된다고 생각하여

방문처리하는 boolean배열을 따로 만들지 않았는데,

방문처리 배열을 도입하여 쓸데없는 동작을 제거해주니 메모리초과가 해결되었다.

메모리: 295940KB

시간: 1456ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static class Node {
        int r;
        int c;
        int dist;

        public Node(int r, int c, int dist) {
            this.r = r;
            this.c = c;
            this.dist = dist;
        }
    }

    static int N, ans;
    static int[][] map;
    static boolean[][] visit;

    static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        StringTokenizer st;
        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 idx = 2;
        visit = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {
                    colorIsland(i, j, idx++);
                }
            }
        }

        ans = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 0) {
                    visit = new boolean[N][N];
                    bfs(i, j, map[i][j]);
                }
            }
        }

        System.out.println(ans);
    }

    private static void bfs(int r, int c, int num) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(r, c, 0));
        visit[r][c] = true;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (int j = 0; j < 4; j++) {
                int nr = node.r + vector[j][0];
                int nc = node.c + vector[j][1];

                if (nr < 0 || nc < 0 || nr >= N || nc >= N || visit[nr][nc]) {
                    continue;
                }

                if (map[nr][nc] == 0) {
                    visit[nr][nc] = true;
                    queue.add(new Node(nr, nc, node.dist + 1));
                } else if (map[nr][nc] != num) {
                    ans = Math.min(ans, node.dist);
                }
            }
        }
    }

    private static void colorIsland(int r, int c, int num) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(r, c, 0));
        visit[r][c] = true;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            map[node.r][node.c] = num;

            for (int i = 0; i < 4; i++) {
                int nr = node.r + vector[i][0];
                int nc = node.c + vector[i][1];

                if (nr < 0 || nc < 0 || nr >= N || nc >= N || map[nr][nc] != 1) {
                    continue;
                }

                if (!visit[nr][nc]) {
                    visit[nr][nc] = true;
                    queue.add(new Node(nr, nc, 0));
                }
            }
        }
    }

}