[백준 2146] 다리 만들기(Java)

최민길(Gale)·2023년 2월 1일
1

알고리즘

목록 보기
28/172

문제 링크 : https://www.acmicpc.net/problem/2146

이 문제는 dfs와 bfs를 동시에 활용하는 문제입니다.

이 문제의 접근을 위해선 크게 두 가지 작업이 필요합니다.

  1. 문제에 주어진 섬들 간의 그룹핑 작업 : 각자 자신이 어떤 섬인지에 대한 정보가 있어야 합니다.
  2. 한 섬에서 다른 섬까지의 최단 거리 구하기 작업

이 떄 1번의 경우 dfs를 이용해서 각 섬에 번호를 부여하여 섬의 ID를 통해 섬을 구별합니다. 2번의 경우 bfs를 이용하여 섬의 외곽 부분에서 상하좌우로 이동하여 바다인 부분을 확장해나간 후 이를 큐에 넣어 경계를 지속적으로 확장해나갑니다.

다음은 코드입니다.

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

public class Main{
    static int N;
    static int res = 10001;
    static int[][] req = new int[101][101];
    static boolean[][] isIslandCheck = new boolean[101][101];
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};

    static void dfs(int y, int x, int islandNum){
        isIslandCheck[y][x] = true;
        req[y][x] = islandNum;

        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny<0 || ny>=N || nx<0 || nx>=N) continue;

            if(req[ny][nx] != 0 && !isIslandCheck[ny][nx]) dfs(ny,nx,islandNum);
        }
    }

    static void enlargeIsland(int[][] map, int islandNum){
        boolean[][] check = new boolean[101][101];
        Queue<Island> queue = new LinkedList<>();

        // 해당 섬을 큐에 추가
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(map[i][j] == islandNum){
                    queue.add(new Island(i,j,0));
                    check[i][j] = true;
                }
            }
        }

        while(!queue.isEmpty()){
            Island position = queue.poll();

            for(int i=0;i<4;i++){
                int ny = position.y + dy[i];
                int nx = position.x + dx[i];
                if(ny<0 || ny>=N || nx<0 || nx>=N) continue;

                // 만약 이동한 값이 다른 섬이었을 경우 현재 cnt값을 res와 비교
                if(map[ny][nx] != islandNum && req[ny][nx] != 0){
                    if(res > position.cnt && position.cnt != 0) res = position.cnt;
                }
                else{
                    // 이동한 좌표가 바다이고 체크되지 않았을 경우
                    if(map[ny][nx]==0 && !check[ny][nx]){
                        check[ny][nx] = true;
                        queue.add(new Island(ny,nx, position.cnt+1));
                    }
                }
            }
        }
    }

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

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                req[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 같은 섬끼리 그룹핑
        int islandNum = 1;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!isIslandCheck[i][j] && req[i][j] != 0){
                    dfs(i,j,islandNum);
                    islandNum++;
                }
            }
        }

        // 각 섬 별로 육지를 확장시켜 다른 육지와 닿았을 때의 값의 최솟값을 구함
        for(int i=1;i<=islandNum;i++){
            int[][] map = req.clone();
            enlargeIsland(map,i);
        }

        System.out.println(res);
    }
}

class Island{
    int y;
    int x;
    int cnt;
    Island(int y, int x, int cnt){
         this.y = y;
         this.x = x;
         this.cnt = cnt;
     }
}

profile
저는 상황에 맞는 최적의 솔루션을 깊고 정확한 개념의 이해를 통한 다양한 방식으로 해결해오면서 지난 3년 동안 신규 서비스를 20만 회원 서비스로 성장시킨 Software Developer 최민길입니다.

0개의 댓글

관련 채용 정보