백준 2146 다리만들기 Java

정답률 30퍼센트의 DFS/BFS문제이다. 머리가 안좋아서인지 내 기준에선 많이 어려운것 같다 ㅠ

이 문제를 푸는방법에는 여러가지가 있다고 하지만 난 간척방법을 택해서 이해하기로 했다.

처음에도 간척하는 식으로 인접한 수를 +1 씩하며 거리를 체크하며 문제에 접근했는데

섬과 섬사이의 가장 짧은 거리를 어떻게 뽑아내야할지를 도저히 생각해내지 못했다.

 

결국 해설을 봐야만 했다.

난 입력받은 배열로만 처리하려고 했는데 그게 실수였다.

이 문제에서 간척방법으로 해결하려면 총 3개의 배열이 필요하다.

 

int [][] a ->입력받은 배열

int [][] d ->섬과 섬사이의 거리

int [][] g -> 섬의 영역을 표시

 

처음엔 g배열에

입력받은 배열에서 섬끼리 숫자를 매겨가며 구분을 한다.

만약 

 

5

1 0 0 0 1

1 1 0 0 1

0 0 0 0 0

0 0 1 0 0

0 1 1 1 0

으로 입력이 주어졌다면

 

 g배열에는

1 0 0 0 2

1 1 0 0 2

0 0 0 0 0

0 0 3 0 0

0 3 3 3 0

이 들어가게 된다.

 

그후에는 d배열에 섬과 섬사의 거리를 bfs로 채워넣는다.

채워넣을 땐 거리만 채워넣을 것 이아니라 

g배열에서도 섬이 확장되는 것을 섬을 구분한 숫자로 채워넣는다.

 

d배열

0 1 2 1 0

0 0 1 1 0

1 1 1 2 1

2 1 0 1 2

1 0 0 0 1

 

이 들어가게 된다 여기서 0은 섬이다.

그리고 다시 g배열에는 bfs를 통해 확장한 것을 표시한다.

[0][0]쪽 부터 반복문이 시작하기 때문에 1쪽이 제일 빨리 bfs가 실행된다.

 

g배열

1 1 1 2 2

1 1 1 2 2

1 1 3 0 2

1 3 3 3 0

3 3 3 3 3

 

이렇게해서 내가 헷갈려했던 가장 빠른 거리를 알아 낼 수 있다.

g배열에서 현재의 위치와 인접한 위치의 숫자가 다를 때 (확장된 섬의 영역이 다를 때)

d배열에서 현재의 위치와 인접한 위치의 거리를 합치면 된다.

이렇게 합친 값중에 가장 작은값이 정답이 되게 된다.

 

나에겐 이해하기도 어렵고 푸는건 더 어렵다...

코드가 길지만 차근차근 살펴보자...

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Q2146 {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] a = new int[n][n]; //입력받은 배열
        int[][] d = new int[n][n]; //거리
        int[][] g = new int[n][n]; //섬 그룹
        for (int i=0; i<n; i++) //입력 받기
            for (int j=0; j<n; j++) 
                a[i][j] = scan.nextInt();
        int cnt = 0; //섬을 표시할 변수
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 1 && g[i][j] == 0) { //a가 1이고 g를 초기화 안했다면
                    Queue<Dot> q = new LinkedList<Dot>();
                    g[i][j] = ++cnt; //g를 초기화
                    q.add(new Dot(i, j));
                    while (!q.isEmpty()) {
                        Dot p = q.remove();
                        int x = p.x;
                        int y = p.y;
                        for (int k=0; k<4; k++) {
                            int nx = x+dx[k];
                            int ny = y+dy[k];
                            if (0 <= nx && nx < n && 0 <= ny && ny < n) 
                                if (a[nx][ny] == 1 && g[nx][ny] == 0) {
                                    q.add(new Dot(nx, ny));
                                    g[nx][ny] = cnt; //while문 안에서 돌기때문에 인접한 다른 곳들도 1이면 같은 숫자로 초기화 
                                }
                        }
                    }
                }
            }
        }
        
        Queue<Dot> q = new LinkedList<Dot>(); //큐 재생성
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                d[i][j] = -1; //d에 우선 -1넣어둔다.
                if (a[i][j] == 1) { 
                    q.add(new Dot(i,j)); //1인곳을 q에 넣어주고
                    d[i][j] = 0; //섬을 0으로 표시
                }
            }
        }
        while (!q.isEmpty()) {
            Dot p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) 
                    if (d[nx][ny] == -1) { //섬이 아닌곳이면
                        d[nx][ny] = d[x][y] + 1; //거리를 1증가
                        g[nx][ny] = g[x][y]; //섬의 영역도 섬을 표시한 같은 숫자로 확장시킨다. 
                        q.add(new Dot(nx,ny)); //bfs
                    }
            }
        }
        int ans = -1; 
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                for (int k=0; k<4; k++) {
                    int x = i+dx[k];
                    int y = j+dy[k];
                    if (0 <= x && x < n && 0 <= y && y < n) 
                        if (g[i][j] != g[x][y])  //인접한 섬의 영역이 다를 때
                            if (ans == -1 || ans > d[i][j] + d[x][y])  //인접한거리+현재거리 최소값 찾기
                                ans = d[i][j] + d[x][y];
                }
            }
        }
        System.out.println(ans);
    }
}
class Dot {
    int x;
    int y;
    public Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}