[BOJ - JAVA] 2146 - 다리 만들기 (BFS)

# 주소

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

2146번: 다리 만들기

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
public class Main{
    static int n,m;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] arr;
    static boolean[][] visit2;
    static boolean[][] visit;
    static int num = 1;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        visit = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        visit2 = new boolean[n][n];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++) {
                if(arr[i][j] > 0 && visit2[i][j] == false)
                    search(i, j);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(arr[i][j] > 0) {
                    visit = new boolean[n][n];
                    int t = bfs(i,j);
                    if(t > 0)
                        min = Math.min(min, t);
                }
            }
        }
        System.out.println(min);
    }
    public static void search(int x, int y) {
        Queue<Point> queue2 = new LinkedList<>();
        queue2.offer(new Point(x, y));
        visit2[x][y] = true;
        arr[x][y] = num;
        while (!queue2.isEmpty()) {
            Point now = queue2.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if(visit2[nx][ny] != false)
                    continue;
                if(arr[nx][ny] > 0){
                    queue2.offer(new Point(nx, ny));
                    visit2[nx][ny] = true;
                    arr[nx][ny] = num;
                }
            }
        }
        num++;
    }
    public static int bfs(int x, int y) {
        Queue<Points> queue = new LinkedList<>();
        visit[x][y] = true;
        queue.offer(new Points(x, y,0));
        while (!queue.isEmpty()) {
            Points now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if (visit[nx][ny] != false) {
                    continue;
                }
                visit[nx][ny] = true;
                if(arr[nx][ny] == arr[x][y])
                    continue;
                if(arr[nx][ny] == 0) {
                    queue.offer(new Points(nx, ny, now.cnt + 1));
                }
                else
                    return now.cnt;
            }
        }
        return 0;
    }
}
class Points{
    int x;
    int y;
    int cnt;
    public Points(int x, int y, int cnt){
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

이 장대한 코드량이 보이십니까.

제가 세어 보니까 정확히 100줄 나오네요.

풀고나니까 엄청 단순한데, 이게 전처리과정을 거쳐야 하는게 좀 실책이었습니다.

이런걸 풀 때 저도 바로는 못풀고 좀 생각을 하고 푸는데 미리 섬의 값을 다른 값으로 바꾼다는 점이 상당히 접근하기 어려웠습니다.

그래서 푸는데 10시간 걸렸어요. (풀면서 딴짓한 것도 많았지만 ㅎ..)

또 10시간이나 걸렸던 결정적인 이유는 다른 분의 포스팅을 거~~~의 보지 않고 (본건 21억 값이 나와서 알고보니까 visit을 != 해줘야 하는데 ==되어있어서 무한참조 에러...)

그리고 비하인드 스토리가 있는데 자꾸 정답이 21억이 나오길래 음... 로또 당첨금액인가 했는데 잘 보니 그냥 정수형이 가지는 최대값이네요. (허허)

어쨌든 이 문제에 대한 해설을 알고 싶어서 오신 분들게 설명을 해야 하니 이제부터 집중해보겠습니다.

 

static int n,m;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static int[][] arr;
static boolean[][] visit2;
static boolean[][] visit;
static int num = 1;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) {

static으로 선언한 구문들을 먼저 살펴보겠습니다.

dx와 dy는 이동할 크기입니다.

기하와 벡터를 배우신 분들은 이걸 기저라고 생각하시면 되겠네요.

그리고 arr는 제 블로그에서 늘 쓰는 기본 배열arr값, visit은 2개 선언했습니다. 한 개로 해도 되지만 거기서 거기.

그리고 min은 가질 수 있는 정수 값중 최대값인 Integer.MAX_VALUE를 가집니다.

자 제일 먼저 arr와 visit을 선언하고 arr를 데이터 입력받습니다.

이중 for문으로 받아와야겠죠?

 

그 다음 visit2을 선언하는데, 이 때에도 이중 for문을 이용합니다.

여기에서 할 과정은 arr의 섬을 각자 다른 값으로 보유하게 할 것입니다.

그래야만 어느 섬에서 다른섬까지 다리를 연결할 때 그 흔적을 알 수 있으니까요.

현재 입력값이 1과 0으로 구분되어 있는데, 위에 있는 어느 섬과 밑의 어느 섬을 연결하려 할 때 둘 다 1이면 구분하기 힘들잖아요?

그래서 각각의 섬을 모두 알아내서 그 섬마다 구분되게끔 다른 값을 가지게 하는 것입니다.

저는 1 , 2 , 3 , ... 으로 했습니다.

이 때 arr값이 0인 부분은 굳이 탐색할 필요가 없으므로 arr가 0보다 크고 방문하지 않은 visit2들만 search문을 돌릴거에요.

왜 visit2를 체크해야할까요?

이 search문도 사실 bfs문인걸 알 필요가 있습니다.

너비우선탐색이란 뜻인데요

너비우선탐색이면 기본적으로 제일 처음 값이 들어왔을 때 인근해있는 모든 값을 다 찾아낼 수 있습니다.

그렇기 때문에 한 번 arr[i][j]에 값이 들어가면 주변의 값을 모두 방문하고 또 우리가 찾는 부분은 섬의 위치이기 때문에 굳이 재방문 할 필요가 없는것이지요.

그러므로 search문을 살펴 보겠습니다.

public static void search(int x, int y) {
    Queue<Point> queue2 = new LinkedList<>();
    queue2.offer(new Point(x, y));
    visit2[x][y] = true;
    arr[x][y] = num;
    while (!queue2.isEmpty()) {
        Point now = queue2.poll();
        for(int i = 0; i < 4; i++){
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                continue;
            if(visit2[nx][ny] != false)
                continue;
            if(arr[nx][ny] > 0){
                queue2.offer(new Point(nx, ny));
                visit2[nx][ny] = true;
                arr[nx][ny] = num;
            }
        }
    }
    num++;

저는 search문을 이렇게 짰습니다.

여기에서도 Queue를 사용해야해서 queue를 선언하고 queue2에는 x,y를 담습니다.

그리고 visit2를 true로 바꾸어주고 arr[x][y] = num해주게 되면 해당 num으로 섬의 값을 바꿀텐데요.

지금 첫 번째 섬을 우리가 방문했다고 가정하면 이 섬의 값은 모두 1이 되어야 합니다.

그리고 while문으로 들어가서 Point now = queue2.poll()하면 현재의 점을 뽑아오고 2가지의 if문을 통해 방문하면 안되는 점을 continue시킵니다.

이후 arr[nx][ny]는 새로 이동할 점의 위치인데, 이 점이 1보다 크면 모두 queue에 담고 visit도 true로 바꾸고 arr값도 num으로 바꾸며 queue를 비우지 않게끔 합니다.

이 과정을 모두 거치고 나면 처음에 넣은 인덱스 값 하나만으로도 모든 인근해있는 섬의 위치를 num으로 바꿀 수 있습니다.

이후 이 과정이 끝나면 num값을 ++해주어서 다음 섬의 위치에는 2가 들어가게, 그 다음엔 3이 들어가게 만들 수 있습니다.

이미 이 과정이 끝났다면 이 다음 과정도 굉장히 쉽습니다. 

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if(arr[i][j] > 0) {
            visit = new boolean[n][n];
            int t = bfs(i,j);
            if(t > 0)
                min = Math.min(min, t);
        }
    }
}

또다시 이중 for문으로 arr값이 0보다 클 때 bfs를 실행하는데요.

이 과정을 거치는 이유는 arr값이 굳이 0인 지점을 탐색할 필요가 없어서이기도 하고 우리가 찾는 것은 특정한 i,j라는 위치의 점에서 다리를 연결할 가장 짧은 것을 찾는 것이 목표이기 때문에 위에처럼 visit을 처음부터 선언할 필요 없이 계속해서 선언해주어 초기화 해야 할 필요가 있습니다.

또한 이 bfs를 t에 담아오고 이 t가 0보다 클 때만 출력함으로써 (사실 굳이 필요는 없는데) min값에 담아, 계속해서 더 짧은 이동경로가 나올때마다 새로 갱신하여 min값에 담아주어 min을 출력하면 그것이 정답이 됩니다.

그럼 이 bfs문은 어떻게 생겼는지 보겠습니다.

public static int bfs(int x, int y) {
    Queue<Points> queue = new LinkedList<>();
    visit[x][y] = true;
    queue.offer(new Points(x, y,0));
    while (!queue.isEmpty()) {
        Points now = queue.poll();
        for (int i = 0; i < 4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                continue;
            if (visit[nx][ny] != false) {
                continue;
            }
            visit[nx][ny] = true;
            if(arr[nx][ny] == arr[x][y])
                continue;
            if(arr[nx][ny] == 0) {
                queue.offer(new Points(nx, ny, now.cnt + 1));
            }
            else
                return now.cnt;
        }
    }
    return 0;

마찬가지로 Queue를 선언하고 queue에 담고 visit도 true로 바꾸어줍니다.

그리고 지금 현재 상태에선 섬이 3개라면 각 섬이 1, 2, 3으로 이루어져 있다는 것을 인지한채로 넘어가겠습니다.

while문으로 들어가고 Points now = queue.poll()라고 했는데, 이 Points는 위의 Point와 다릅니다.

위의 Point는 import.java.awt.Point할 때의 그 Point이기 때문에 기본적으로 인자를 2개의 int형만 받습니다.

근데 우리가 하고 싶은건 점의 위치도 챙기면서 이동거리도 +1씩 해주려면 이 현재의 cnt값도 알아야하기 때문에 또다른 구문이 필요한데요.

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

그래서 저는 제일 밑에 Point의 class를 새로 만들고 오버라이딩했습니다.

어쨌든 이 과정을 통해 Queue를 제네릭에 담을 수 있습니다.

이후 nx와 ny의 값을 지정해주고 2가지의 if문을 통해 예외의 상황을 continue해줍니다.

visit값은 이제 true로 바꾸고 그 다음이 중요한데, arr[nx][ny] == arr[x][y] continue해야합니다.

그러니까, arr의 새로 이동한 위치가 현재 원래 삽입된 arr값이랑 같으면 과감하게 버려야한다는 뜻입니다.

왜냐하면 같은 섬의 위치니까 같은거겠죠?

제가 그래서 섬의 위치를 다 숫자마다 다르게 한 이유입니다.

결과적으로 arr가 0이 나와야 다시 queue에 담으면서 이동거리를 now.cnt + 1씩 해주어 증가시킬 수 있습니다.

또한 arr값이 0이 아니라면, 앞의 전처리 과정에서 모두 걸러졌으므로 새로운 섬에 도착했다는 것을 의미하여 now.cnt를 return해주면 그것이 정답이 되겠습니다.

 

 

감사합니다.