[백준/BOJ/JAVA] 2146 다리 만들기

 

 

이 나라는 N×N크기의 이차원 평면상에 존재한다.

이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다.

 

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다.

이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다.

 

위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 두 대륙을 연결하는 가장 짧은 다리의 길이를 구하는 문제

 

 

먼저 섬끼리 구분을 할 수 있도록 넘버링을 해준다.

 

넘버링 메서드 makeLand

private static void makeLand(int x, int y) {
    Queue<int[]> que = new LinkedList<>();
    que.add(new int[] {x, y});
    visited[x][y] = true;
    map[x][y] = num;

    while (!que.isEmpty()) {
        int[] now = que.poll();

        for (int i=0; i<4; ++i) {
            int nextX = now[0] + dx[i];
            int nextY = now[1] + dy[i];

            if (nextX>=0 && nextY>=0 && nextX<N && nextY<N){
                if(map[nextX][nextY]==1 && !visited[nextX][nextY]){
                    visited[nextX][nextY] = true;
                    map[nextX][nextY] = num;
                    que.add(new int[] {nextX, nextY});
                }
            }
        }
    }
}

전역 변수 num을 사용하여 넘버링을 해준다.

 

 

main

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    N = Integer.parseInt(br.readLine());

    visited = new boolean[N][N];
    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());
        }
    }

    // 섬에 번호 부여
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(!visited[i][j] && map[i][j]!=0){
                makeLand(i,j);
                ++num;
            }
        }
    }

    // visited 초기화
    clear_visited();

    // 다리만들기
    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, map[i][j]);
                clear_visited();
            }
        }
    }

    System.out.println(res);
}

넘버링이 끝나면 방문 여부를 체크하기 위해 만든 배열 visited를 초기화하고 bfs를 실행시킨다.

다른 섬에 도달했을 때 리턴되므로 계속 visited를 초기화 해야한다.

 

 

bfs

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

    while(!que.isEmpty()){
        point temp = que.poll();
        int nowX = temp.x;
        int nowY = temp.y;
        int cnt = temp.cnt;

        for(int i=0; i<4; i++){
            int nextX = nowX + dx[i];
            int nextY = nowY + dy[i];

            if(nextX>=0 && nextY>=0 && nextX<N && nextY<N){
                if(!visited[nextX][nextY]){
                    // 다리놓기
                    if(map[nextX][nextY]==0){
                        visited[nextX][nextY] = true;
                        que.offer(new point(nextX, nextY, cnt+1));
                    }
                    // 다른 섬 도달, 다리 길이 비교
                    else if(map[nextX][nextY]!=0 && map[nextX][nextY]!=start){
                        res = Math.min(res, cnt);
                        que.clear();
                        return;
                    }
                }
            }
        }
    }
}

상하좌우 돌아가며 다리를 놓아준다 (=1씩 더해준다)

만약 다른 섬에 도달했다면, 최솟값을 구하여 결과값 변수 res에 저장한다.

(res는 Integer.MAX_VALUE로 초기화 된 상태)

큐의 값들을 모두 지우고, return 해준다.

return 후엔 main에서 visited를 초기화 한 뒤, 다시 다른 섬에서 bfs를 시작한다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ_2146 {
    static final int[] dx= {0,0,1,-1};
    static final int[] dy = {1,-1,0,0};
    static int[][] map;
    static boolean[][] visited;
    static int N, num=1, res=Integer.MAX_VALUE;
 
    static class point{
        int x;
        int y;
        int cnt;
 
        point(int x, int y, int cnt){
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
 
        visited = new boolean[N][N];
        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());
            }
        }
 
        // 섬에 번호 부여
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j] && map[i][j]!=0){
                    makeLand(i,j);
                    ++num;
                }
            }
        }
 
        // visited 초기화
        clear_visited();
 
        // 다리만들기
        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, map[i][j]);
                    clear_visited();
                }
            }
        }
 
        System.out.println(res);
    }
 
    // 섬에 번호 부여
    private static void makeLand(int x, int y) {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[] {x, y});
        visited[x][y] = true;
        map[x][y] = num;
 
        while (!que.isEmpty()) {
            int[] now = que.poll();
 
            for (int i=0; i<4; ++i) {
                int nextX = now[0] + dx[i];
                int nextY = now[1] + dy[i];
 
                if (nextX>=0 && nextY>=0 && nextX<N && nextY<N){
                    if(map[nextX][nextY]==1 && !visited[nextX][nextY]){
                        visited[nextX][nextY] = true;
                        map[nextX][nextY] = num;
                        que.add(new int[] {nextX, nextY});
                    }
                }
            }
        }
    }
 
    // 다리만들기
    public static void bfs(int x, int y, int start){
        Queue<point> que = new LinkedList<>();
        que.add(new point(x, y, 0));
        visited[x][y] = true;
 
        while(!que.isEmpty()){
            point temp = que.poll();
            int nowX = temp.x;
            int nowY = temp.y;
            int cnt = temp.cnt;
 
            for(int i=0; i<4; i++){
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];
 
                if(nextX>=0 && nextY>=0 && nextX<N && nextY<N){
                    if(!visited[nextX][nextY]){
                        // 다리놓기
                        if(map[nextX][nextY]==0){
                            visited[nextX][nextY] = true;
                            que.offer(new point(nextX, nextY, cnt+1));
                        }
                        // 다른 섬 도달, 다리 길이 비교
                        else if(map[nextX][nextY]!=0 && map[nextX][nextY]!=start){
                            res = Math.min(res, cnt);
                            que.clear();
                            return;
                        }
                    }
                }
            }
        }
    }
 
    // visited 초기화
    private static void clear_visited(){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                visited[i][j] = false;
            }
        }
    }
}
 

 

어려웠다..^^ 다른 블로그 싹싹 뒤져서 풀었다..

[JAVA]백준2146번 다리 만들기