백준 1600번 자바 문제 풀이

1600번: 말이 되고픈 원숭이

문제 해석

1,1에 정점에서 h, w의 정점까지 이동하는데 k번만 체스판의 말과 같이 이동할 수 있고 그 외에는 인접한 정점으로만(상, 하, 좌, 우) 움직일 수 있을 때 h, w까지 이동하는 최소 경로수를 구하는 문제이다.

 

내가 푼것

처음에 문제를 보고 k번 말처럼 움직이고 그 외에는 인접한 좌표로 움직이면서 BFS 탐색을 하면 되겠구나! 싶었다.

    public static int[] horseMoveX = {-2,2,-1,1};
    public static int[][] horseMoveY = {{-1,1},{-1,1},{-2,2},{-2,2}};
    public static int[] normalMoveX = {1,-1,0,0};
    public static int[] normalMoveY = {0,0,1,-1};

그래서 2가지의 이동 경로를 다루기 위해 말 처럼 움직이기 위한 X, Y 좌표를 정의하여 주었고

인접한 정점으로만 움직일 수 있는 X,Y 좌표를 정의하여 주었다.

 

if(horseMoveCount < k)
    {
        for(int i = 0;i<4;++i)
        {
            for(int t = 0;t<2;++t)
            {
                int tempX = node.x + horseMoveX[i];
                int tempY = node.y + horseMoveY[i][t];

                if(tempX <= 0 || tempY <= 0 || tempX > h || tempY > w)
                {
                    continue;
                }else if(visited[tempX][tempY] || map[tempX][tempY]==1)
                {
                    continue;
                }else{
                    queue.offer(new Node(tempX,tempY));
                    visited[tempX][tempY] = true;
                    answerMap[tempX][tempY] = answerMap[node.x][node.y]+1;
                    ++horseMoveCount;
                }
            }
        }
    }

말의 움직임을 체크하는 horseMoveCount변수가 k보다 작으면 말처럼 이동할 수 있는 횟수를 아직 사용을 덜 한 것이기 때문에 

위에서 정의했던 말처럼 움직이는 X, Y좌표의 값들을 받아서 말 처럼 움직였을 때의 X,Y 좌표가 장애물이 있지 않은 길이고 아직 탐색하지 않은 정점이라면 현재 좌표에서 말 처럼 움직이는 것이 가능하다는 것이기 때문에 queue에 X,Y 좌표를 추가하는 방식으로 구현하였다.

 

반례

0	0	0
0	0	0
0	1	1
0	1	0

내가 설계했던 코드의 반례이다. 내가 설계했던 코드를 이용하게 되면 위와 같은 방식의 길은 탐색할 수 없다고 계산된다.

나의 코드에 따르면 처음에 1,1에서 시작할 때 horseMoveCount가 k가 0이 아닌 이상 당연히 작을 것이다.

만약 K = 1이라면 1,1에서 2,3으로 말처럼 이동하고 말 이동 횟수를 전부 사용했기 때문에 4,3에는 접근할 수가 없다.

 

하지만 실제로는 1,1에서 아래쪽으로 2번 이동하고 3,1에서 오른쪽 대각선으로 말처럼 이동하면 4,3에 접근을 할 수 가 있다.

이 반례를 통해 배울 수 있는 것은 이미 탐색한 정점이라도 최적의 경로가 아닐 수 도 있고 각 정점마다 말 처럼 이동할 수 있는 경로가 존재한다는 뜻 즉 한번 탐색한 정점이라고 해서 다시 탐색하지 않아도 되는 것이 아니라는 점이다.

 

원숭이처럼 움직이다가 말처럼 움직이는 경로가 최적의 경로가 될 수도 있고 말처럼 처음에 몇번 움직이고 원숭이처럼 움직이는 경로가

최적의 경로가 될 수도 있다는 점이다.

 

풀이

static boolean[][][] visited;

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

while(!queue.isEmpty())
{
    Node node = queue.poll();
    if(node.x == h-1 && node.y == w-1)
    {
        return node.count;
    }
    for(int i =0;i<4;++i)
    {
        int mx = node.x + normalMoveX[i];
        int my = node.y + normalMoveY[i];
        if(mx>=0 && my >= 0 && mx < h && my < w && visited[mx][my][node.k] == false && map[mx][my] == 0)
        {
            visited[mx][my][node.k] = true;
            queue.offer(new Node(mx,my,node.count+1,node.k));
        }
    }
    if(node.k < k)
    {
        for(int i=0; i<8;++i)
        {
            int hx = node.x + horseMoveX[i];
            int hy = node.y + horseMoveY[i];
            if(hx>=0 && hy >= 0 &&  hx < h && hy < w && visited[hx][hy][node.k+1] == false && map[hx][hy] == 0)
            {
                visited[hx][hy][node.k+1] = true;
                queue.offer(new Node(hx,hy,node.count+1,node.k+1));
            }
        }
    }

각각의 정점마다 말 처럼 움직일 경우의 수가 있기 때문에 3차원 배열로 선언해 준다.

예를 들면 visited [1][2][1] = true라고 하면 1,2 좌표로 말처럼 한번 이동해서 왔다는 것을 의미한다. 

 

그리고 class에 새로운 값인 k와 count를 추가해 준다. 앞서 말했던 것처럼 1,2 좌표로 말처럼 한번 이동해서 온 class 객체를 만들어줘서

Queue에 추가하면 큐에 이미 있는 정점들을 탐색을 하다가 1,2 좌표를 가지고 말처럼 한번 이동해서 온 정점을 탐색하기 시작할 것이다.

 

현재 큐에서 꺼내온 객체의 k의 값은 1이다. 말의 이동 제약이 1번으로 주어 졌다면 현재 객체는 더 이상 말처럼 이동할 수 없기 때문에 

인접한 정점들만 탐색을 할 수 있다. 그래서 if(node.k < k)라는 조건이 주어서 현재 탐색하는 객체가 말 처럼 이동할 수 있는 제약 횟수를

넘지 않았는지 확인을 한다.

 

이와 같은 3차원 배열을 이용해 내가 실패했던 반례인 각각의 정점마다 말 처럼 이동할 수 있는 경우의 수, 즉 원숭이처럼 이동하다가 말처럼 럼 이동하는 반례를 처리해 줄 수가 있다.

 

내 생각에 핵심은 하나의 정점이 있을 때 해당 정점까지 온 경우의 수를 각기 다른 객체로 처리해서 모든 경우의 수를 처리하는 것 같다.

예를 들어 {2,3} 좌표에 왔을 때 말의 이동 기술을 1번 써서 온 객체, 이동 기술을 2번 써서 온 객체... 등으로 서로 다른 객체로 판별해

모든 경우의 수를 계산하는 게 핵심인 것 같다.

 

꽤 어려운 아니 많이 어려운 문제인 거 같다. 코드를 보고 해석하는데도 오래 걸렸고 코드가 어떻게 굴러가는지 머릿속으로 생각하는데도 

오래 걸린 문제다.. 2차원 배열로 푸는 것도 버거운데 3차원 배열?! 재밌네...

 

import java.util.*;
public class Main{
    static int k, w, h;
    static int[][] map;
    static int min = Integer.MAX_VALUE;
    static int[] horseMoveX = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] horseMoveY = {-1, 1, -2, 2, -2, 2, -1, 1};
    static int[] normalMoveX = {1,-1,0,0};
    static int[] normalMoveY = {0,0,1,-1};
    static boolean[][][] visited;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        k = sc.nextInt();
        w = sc.nextInt();
        h = sc.nextInt();

        map = new int[h][w];
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        visited = new boolean[h][w][k + 1];
        min = bfs(0, 0);

        if(min == Integer.MAX_VALUE)
        {System.out.println(-1);}
        else
        {System.out.println(min);}

    }

    public static int bfs(int x,int y)
    {
        Queue<Node>queue = new LinkedList<>();
        queue.offer(new Node(x,y,0,0));
        visited[x][y][0] = true;

        while(!queue.isEmpty())
        {
            Node node = queue.poll();
            if(node.x == h-1 && node.y == w-1)
            {
                return node.count;
            }
            for(int i =0;i<4;++i)
            {
                int mx = node.x + normalMoveX[i];
                int my = node.y + normalMoveY[i];
                if(mx>=0 && my >= 0 && mx < h && my < w && visited[mx][my][node.k] == false && map[mx][my] == 0)
                {
                    visited[mx][my][node.k] = true;
                    queue.offer(new Node(mx,my,node.count+1,node.k));
                }
            }
            if(node.k < k)
            {
                for(int i=0; i<8;++i)
                {
                    int hx = node.x + horseMoveX[i];
                    int hy = node.y + horseMoveY[i];
                    if(hx>=0 && hy >= 0 &&  hx < h && hy < w && visited[hx][hy][node.k+1] == false && map[hx][hy] == 0)
                    {
                        visited[hx][hy][node.k+1] = true;
                        queue.offer(new Node(hx,hy,node.count+1,node.k+1));
                    }
                }
            }
        }
        return min;
    }
}

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