BJ G3 2146 다리만들기

BJ G3 2146 다리만들기

 

 

문제링크

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

2146번: 다리 만들기

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=oTIE6tc8zYA&feature=youtu.be

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;


public class BJ_G4_2146_다리만들기 {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    static int N, A, islandIdx;
    static int[][] map;
    static boolean[][] visited;
    static List<Point> points;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));

        N = Integer.parseInt(br.readLine());// N(100이하의 자연수)
        map = new int[N][N];
        visited = new boolean[N][N];
        StringTokenizer tokens = null;
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }

        points = new LinkedList<>();
        islandIdx = 2;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (map[r][c] == 1) {
                    bfsMarkIslandNum(r, c);
                    islandIdx++;
                }
            }
        }

        /*
        System.out.println("섬 정보 확인");
        for (int[] row : map) {
            System.out.println(Arrays.toString(row));
        }*/

        // 각 섬에서 다른 섬까지 최단 거리 찾아보기.
        A = Integer.MAX_VALUE;
        for (Point p : points) {
            bfsGetShortBridgeLength(p);
        }
        System.out.println(A);
    }

    static void bfsGetShortBridgeLength(Point p) {
        Queue<Point> q = new LinkedList<>();
        q.offer(p);
        for (boolean[] row : visited) {
            Arrays.fill(row, false);
        }

        while (!q.isEmpty()) {
            Point front = q.poll();
            if (front.d >= A) {
                System.out.println("불필요");
                break;
            }
            for (int d = 0; d < dirs.length; d++) {
                int nr = front.r + dirs[d][0];
                int nc = front.c + dirs[d][1];

                // 범위 안에 있고 미방문 지점이면 가보자.
                if (isIn(nr, nc) && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    // 내륙으로 들어가는 것은 관심 없다.
                    if (map[nr][nc] == front.id) {
                        continue;
                    }
                    // 그 지점이 0이면 다리 놓기로 전진한다.
                    else if (map[nr][nc] == 0) {
                        q.offer(new Point(nr, nc, front.d + 1, front.id));
                    }
                    // 현재 지점과 다른 값이면 거기가 신대륙!! 거리 계산
                    else if (map[nr][nc] != front.id) {
                        A = Math.min(A, front.d);
                        return;
                    }
                }
            }
        }
    }

    static void bfsMarkIslandNum(int r, int c) {
        Queue<Point> q = new LinkedList<>();
        Point p = new Point(r, c, 0, islandIdx);
        q.offer(p);
        map[r][c] = islandIdx;

        points.add(p);

        while (!q.isEmpty()) {
            Point front = q.poll();

            for (int d = 0; d < dirs.length; d++) {
                int nr = front.r + dirs[d][0];
                int nc = front.c + dirs[d][1];

                if (isIn(nr, nc)) {
                    if (map[nr][nc] == 1) {
                        map[nr][nc] = islandIdx;
                        p = new Point(nr, nc, 0, islandIdx);
                        q.offer(p);
                        points.add(p);
                    }
                }
            }
        }
    }

    static boolean isIn(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }

    static class Point {
        int r, c, d, id;

        public Point(int r, int c, int d, int id) {
            this.r = r;
            this.c = c;
            this.d = d;
            this.id = id;
        }

        @Override
        public String toString() {
            return "[" + r + "," + c + "," + d + "]";
        }


    }

    private static String src = "10\r\n" +
                                "1 1 1 0 0 0 0 1 1 1\r\n" +
                                "1 1 1 1 0 0 0 0 1 1\r\n" +
                                "1 0 1 1 0 0 0 0 1 1\r\n" +
                                "0 0 1 1 1 0 0 0 0 1\r\n" +
                                "0 0 0 1 0 0 0 0 0 1\r\n" +
                                "0 0 0 0 0 0 0 0 0 1\r\n" +
                                "0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 1 1 0 0 0 0\r\n" +
                                "0 0 0 0 1 1 1 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0";
}