[BOJ] 백준 2143 - 다리 만들기 (자바)

BFS + DFS

BFS 와 DFS 둘 다 사용해서 푼 문제이다.

BFS와 DFS 의 개념을 알면 힘들게 풀지는 않을 수 있다.

나는 이렇게 푸는게 맞는지 모르겠지만 풀이를 써보겠습다.

풀이

1. 나는 섬에 각각 라벨링을 하여 번호를 매겨줬다.

첫번째 섬은 2의 값으로 두번째 섬은 3의 값으로 세번째 섬은 4의 값으로 매겼다. 이때 DFS를 사용했습니다.

섬에 숫자를 다르게 매겨준 이유는 다리를 놓을때 같은 섬 사이에 다리를 놓으면 문제가 생기기 때문에 다른 값으로 설정

2. 섬의 모든 점에서 다리를 놓기 시작한다. 최단거리는 상,하,좌,우 어디에서 생길지 모르기 때문... 섬의 한 가운데라면 조건을 이용해서 다리 안놓게 해도

되는데 나는 그냥 전체 BFS 돌려버렸다. 어차피 반복문 4번만 하면 빠져 나오니깐;

3. 섬의 모든점에서 다리를 놓는데 다리는 같은섬에 놓지 못하고 바다일 때만 놓을 수 있다. 즉 다음 방문지가 0값을 가지고 있을 때 다리를 놓을 수 있다.

그리고 이미 다리를 놓은 값은 -1로 설정하여 무한루프에 빠지지 않게 설정해줘야 한다. (-1로 설정해줬기 때문에 배열을 초기화 해줘야함)

나는 배열 초기화 때문에 reset[][] , arr[][] 함수를 2개 사용 했다.

4. 다리를 놓으면서 현재 자기섬의 값이 아닌 다른 섬에 도착하였을 때 BFS를 종료시켜주면 된다.(return 함수 사용)

최단 거리를 비교하여 변수에 저장시켜주고 나중에 출력시켜주면 끄읏.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
 
import javax.rmi.ssl.SslRMIClientSocketFactory;
 
public class Main {
    static int[][] arr;
    static int[][] reset;
    static int N;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int count = 1;
    static int min = Integer.MAX_VALUE;
 
    public static void main(String args[]) throws Exception {
        //BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        reset = new int[N][N];
        arr = new int[N][N];
        
        for (int i = 0; i < N; i++) {
            String[] str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                reset[i][j] = Integer.parseInt(str[j]);
            }
        }
        //-----------------입력부------------------\\
        
        //다리를 건너기전에 해야 할 일이 하나 있다.
        //섬 마다 번호를 붙혀줘야한다. 아래 DFS는 번호를 붙혀주는 작업을 한다.
        //1번째 방문하는 섬은 2번으로 2번째는 3번으로 ...
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (reset[i][j] == 1) {
                    count++;
                    reset[i][j] = count;
                    Labeling_DFS(i, j);
                }
            }
        }
        Reset();    //arr함수를 reset 함수로 초기화 시켜줌. (복사)
        
        //가장 가까운 다리길이를 찾는 과정
        //섬에서 시작하여 다른 섬에 가장 빨리 도착할 때 값을 저장하고 돌아온다.
        //섬의 모든 지점에서 확인한다. 상하좌우에 섬이 있을 수 있고 최단거리가 될 수 있으므로
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] != 0) {
                    ShortestPath_BFS(i, j);
                    Reset();
                }
            }
        }
        System.out.println(min);
 
    }
 
    public static void Labeling_DFS(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            //좌표 넘어가면 패스
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
                continue;
            }
            //다음 갈 위치가 같은 섬이면 패스
            if (reset[nextX][nextY] == count) {
                continue;
            }
            //다음 갈 위치가 바다이면 패스
            if (reset[nextX][nextY] == 0) {
                continue;
            }
            //섬의 번호를 count로 통일한다. (count는 2,3,4 등등 순으로 증가한다)
            reset[nextX][nextY] = count;
            Labeling_DFS(nextX, nextY);
        }
 
    }
 
    public static void ShortestPath_BFS(int x, int y) {
        
        //inX, inY 는 출발 섬의 값을 저장하기위한 좌표이다.
        int inX =x;    //출발 섬의 x좌표
        int inY = y; //출발 섬의 y좌표
        Queue<Dot> q = new LinkedList<Dot>();
        q.add(new Dot(x, y,0));
 
        while (!q.isEmpty()) {
            Dot current = q.poll();
            for (int i = 0; i < 4; i++) {
                //다음 간척사업할 위치좌표와 거리 저장 변수
                int nextX = current.x + dx[i];
                int nextY = current.y + dy[i];
                int nextCount = current.count + 1;
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
                    continue;
                }
                //다음 간척할 자리가 이미 섬이라면 패스
                if (arr[nextX][nextY] == arr[inX][inY]) {
                    continue;
                }
                //다음 간척할 자리가 이미 간척한 자리라면 패스
                if(arr[nextX][nextY]==-1){
                    continue;
                }
                //다음 간척할 자리가 바다가 아니라면
                //이미 섬과 간척자리는 위에 조건에 걸렸으므로 이 조건일 때는 무조건 다른 섬이다.
                if(arr[nextX][nextY]!=0){
                    //다른 섬에 도착했을때의 최단거리를 비교하여 저장. 그리고 리턴
                    min = Math.min(min, nextCount-1);
                    return;
                }
                //간척한 자리는 -1로 놓는다. 그리고 큐에 넣는다.
                arr[nextX][nextY] = -1;
                q.add(new Dot(nextX,nextY,nextCount));
                
            }
        }
 
    }
 
    //간척사업으로 인해 -1로 변한 자리를 되돌려 놔야 다른 최단거리를 구할 수 있다.
    public static void Reset() {
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                arr[i][j] = reset[i][j];
            }
        }
    }
 
}
 
class Dot {
    int x;
    int y;
    int count;
    Dot(int x, int y,int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}