[알고리즘][BOJ][2146] 다리 만들기

[알고리즘][BOJ][2146] 다리 만들기

 

 

문제

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

 

 

풀이

꽤 시간을 많이 쏟은 문제입니다. 쉽지 않았어요. 풀고나니 잘 풀 수 있을 거라고 느껴지지만 처음 문제를 볼 땐 많이 헤맸습니다. 다음에 꼭 복습해서 숙달시키려구요.

 

육지의 번호를 입력받은 후 BFS로 육지마다 번호를 다르게 매겨서 구분해줍니다.

for문을 돌려 1을 발견하면 Numbering_BFS에 들어갑니다. 그리고 이 때, count변수를 통해 육지 번호표를 매깁니다. BFS로 탐색을 해서 육지가 나타날 때마다 count변수를 올려서 번호표를 붙혀줘요. 

 

그 다음은 다리 놓기 입니다.

땅마다 각기 다른 번호표가 매겨져 있습니다. 이 번호표를 하나씩 넓혀 땅을 차지하는 땅따먹기 방식입니다. 이 때, check배열을 초기화 시켜주고 bridge배열을 새로 만듭니다. check배열은 방문 여부 확인, bridge 배열은 다리 놓기, map배열은 몇 번 땅이 그 자리를 차지했는지 표시해주는 용도로 사용합니다. BFS를 이용해 다리를 놓고 bridge배열에 다리 번호를 입력해줍니다. 만약, 각기 다른 땅(map[x][y] != map[nx][ny])이 마주했다면 bridge에 입력된 수를 더해주면 다리의 길이가 나타납니다. 이 수를 list에 더해서 min값을 답으로 내줍니다.

 

여기서 또 헤맸던 것이 min값의 기본값입니다. 다리의 최대 길이는 n이 최대라고 생각해서 이걸로 이틀을 헤맸네요. 다리의 최대 길이는 사각형의 대각선 길이 입니다. (루트 n^2 * n^2) 

 

 

 

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int n;

    static int[][] map;
    static boolean[][] check;
    static int[][] bridge;

    static Queue<Node> q = new LinkedList<>();
    static ArrayList<Integer> list = new ArrayList<>();
    
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        map = new int[n][n];
        check = new boolean[n][n];

        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                map[i][j] = scan.nextInt();
            }
        }
        
        int count = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                //육지 마다 번호를 다르게 매겨 구분해줌
                if(map[i][j]==1 && !check[i][j]) {
                    Numbering_BFS(i, j, ++count);
                    
                }
            }
        }

        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                //섬의 인덱스를 큐에 저장
                if(map[i][j]!=0) {
                    q.add(new Node(i,j));
                }
            }
        }
        
        //다리 길이 count할 배열
        bridge = new int[n][n];
        check = new boolean[n][n];
        BFS(); //큐에 저장된 좌표로 영역 확장 및 다리길이 count
        
        //ans 기본값 설정    
        int ans = Integer.MAX_VALUE;
        for(int v : list) {
            if(ans>v) {
                ans = v;
            }
        }
        
        System.out.println(ans);
        
    }
    
    //땅 번호 매기기
    static void Numbering_BFS(int i, int j, int k) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(i, j));
        map[i][j]=k;
        check[i][j]=true;
        
        while(!queue.isEmpty()) {
            i = queue.peek().x;
            j = queue.peek().y;
            queue.poll();
            
            for(int p=0;p<4;p++) {
                int nx = i + dx[p];
                int ny = j + dy[p];
                
                if(0<=nx && nx<n && 0<=ny && ny<n) {
                    if(map[nx][ny]==1 && !check[nx][ny]) {
                        queue.add(new Node(nx, ny));
                        map[nx][ny] = k;
                        check[nx][ny] = true;
                    }
                }
            }
        }
    }
    
    //다리 놓기
    static void BFS() {
        while(!q.isEmpty()) {
            int x = q.peek().x;
            int y = q.peek().y;
            q.poll();
            
            for(int i=0;i<4;i++) {
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(0<=nx && nx<n && 0<=ny && ny<n) {
                    //다리 놓기 완성 --> 각자 놓인 다리 수 더하기
                    if(map[nx][ny]!=0 && map[nx][ny]!=map[x][y]) {
                        list.add(bridge[nx][ny]+bridge[x][y]);
                    }
                    
                    //다리 놓기
                    if(map[nx][ny]==0) {
                        q.add(new Node(nx, ny));
                        map[nx][ny] = map[x][y];
                        bridge[nx][ny] = bridge[x][y]+1;
                    }
                }
            }
        }
    }
}

//좌표 클래스
class Node{
    int x, y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}