백준 No.2665 미로만들기 - JAVA

 

문제

nxn 바둑판 모양으로 총 n제곱개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흐니 방 사이에는 문이 있어서 지나다닐 수 있다. 우니줄 맨 왼쪽 방은 시작방으로서 항상 흰방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. 

 

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데 아래 그림의 경우에는 시작 방에서 끝방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은방(예를 들어 (4,4의 방과 (7,8)의 방) 을 흰 방으로 바꾸면 , 시작 방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오

단, 검은 방을 하나도 흐니방으로 바꾸지 않아도 되는 경우는 0이 답이다.

8
11100110
11010010
10011010
11101100
01000111
00110001
11011000
11000111

 

풀이

- dx, dy를 만들어서 상하좌우를 탐색할 수 있도록 1차원 배열을 만들어야 한다.

- map[][] 2차원 배열을 통해 주어진 입력값을 하나씩 담아야한다.

- dist[][] 검은방을 흰방으로 바꾼 횟수를 각 기록해야하므로 map과 크기가 같은 2차원 배열을 생성한다.

 

일단 문제에서 1은 흰방이고 0은 검은 방이다 1과 1이 붙어있다면 이동할 수 있고 바꿀 필요가 없으므로 dist에는 0을 넣으면 된다. 이게 2차원적으로 생각하면 어렵지만 숫자로 일단 먼저 보면

(주어진 입력 값으로 할 경우)

map[0][0]은 1이다 map[0][0] 은 결국 흰방이라는 뜻이다. 이때 탐색을 dx,dy 배열을 통해 해야한다. 

 

dx = {0,1,0,-1}

dy = {1,0,-1,0} 로 탐색을 한다.

(x가 행이고, y가 열이다 , 좌표로 생각하면 어려우니 배열로 바라봐야 한다.)

for문을 4번 돌리면 상하좌우를 다 볼 수 있다.

 

i = 0 일떄 dx = 0,dy = 1   오른쪽

i = 1 일때 dx = 1,dy = 0    아래

i = 2 일때 dx = 0,dy = -1   왼쪽

i =  3 일때 dx = -1,dy = 0   위

 

이렇게 탐색을 시도하는데 여기서 의문이 들 수 있다. 만약 현재 위치가 0,0 일 경우? 또는 마지막 끝 위치인 (N,N)인경우?

이런 경우에 상하좌우를 탐색할 경우 입력에서 주어지지 않은 영역까지 탐색해버리는 말도 안되는 상황이 펼쳐진다.

그렇기에 if( nextX >= 0 && nextY >= 0 && nextX < N && nextY <N) 으로 먼저 걸러줘야 한다.

여기서 nextX와 nextY는 현재 Node(x,y) 값에 위에 주어진 dx, dy를 더 한 값이므로 상대적으로 변한다.

 

이런 방식으로 탐색하고 먼저 bfs() 메소드를 보면

해당 문제는 너비 탐색을 하면서 다익스트라로 최단까지 구해야 하므로 당연히 Queue를 사용해야한다. 모든 값을 기록하는 것이기에 그냥 Queue를 사용하면 된다. 첫 시작은 0,0 이므로 바로 add 하면 된다. 그리고 문제에서 주어진 것 처럼 첫 시작은 항상 흰방이 주어진다 하여 dist 값에는 0을 넣으면 된다.

 

이제 탐색을 시작하면 된다. queue가 빌때까지 반복하면서 하나씩 값을 꺼내서 x,y값을 꺼내고 그 값에 아까 만든 dx, dy를 더해서 상하좌우에 노드를 탐색하면 된다. 

먼저 if(dist[next][nextY] > dist[now.x][now.y])  이 부분을 보면 dist 배열은 시작부터 Integer.MAX_VALUE로 제일 큰 값을 넣었기 때문에 처음 방문하는 곳이라면 한 번은 무조건 통과한다. 

if(map[nextX][nextY] == 1) 이 말은 상하좌우 탐색 중 해당 노드가 흰 방이냐고 묻는 것이다. 맞다면

dist[nextX][nextY] = dist[now.x][now.y] 하는데 흰방이므로 바꿀 필요가 없다는 것이다.

만약 내가 0,0에 있는데 0,1이 흰방이면 굳이 안 바꿔도 되므로 dist에도 바꾸지 않고 이동했다고 기록을 남기는 것이다.

만약 탐색하는 위치가 1이 아니라 0(검은방) 일 경우 바꿔야 하므로 dsit에 현재 노드보다 1큰 값을 dist에 넣어줘야 한다.

그러고 나서 다음 노드에 이동해서 계속 탐색을 이어나가야 하므로 Queue에 다음 노드를 추가한다.

 

 

탐색 시작 전 배열을 가장 큰 값으로 초기화시킨다. dist 는 2차원배열이다

탐색 맨 시작은 

 

 

마지막으로 dist 배열을 출력해보면

이런 결과를 볼 수 있다 입력 값이 

8
11100110
11010010
10011010
11101100
01000111
00110001
11011000
11000111

이므로 손으로 풀어봐도 저런 답이 나오는 걸 알 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    static int map[][];
    static int dx[] = {0,1,0,-1};
    static int dy[] = {1,0,-1,0};
    static int dist[][];
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dist = new int[N][N];

        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<N;j++){
                map[i][j] = str.charAt(j)-'0';
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
        bfs();


        System.out.println(dist[N-1][N-1]);	//배열은 0부터 시작이므로 
    }
    public static void bfs(){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0,0));   //시작점
        dist[0][0] = 0;

        while(!q.isEmpty()){
            Node now = q.poll();

            for(int i=0;i<4;i++){   //상하좌우 탐색
                int nextX = now.x+dx[i];
                int nextY = now.y+dy[i];

                if(nextX >=0 && nextY >= 0 && nextX < N && nextY < N){
                    if(dist[nextX][nextY] > dist[now.x][now.y]){
                        if(map[nextX][nextY] == 1) dist[nextX][nextY] = dist[now.x][now.y];
                        else dist[nextX][nextY] = dist[now.x][now.y]+1; //이동
                        q.add(new Node(nextX,nextY));
                    }
                }
            }
        }
    }


    public static class Node{
        int x;
        int y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}