자바(백준) 1600 말이 되고픈 원숭이

오답 노트 & 새로 알게 된 점

처음에 이 문제를 풀었을 때 어렵지 않은 bfs인 것 같았다.

그래서 예제를 다 맞고서 제출을 했지만 계속해서 틀렸다.

 

혼자서 반례를 생각해보니 visit배열을 이차원으로 했을 때 문제가 생긴다.

 

2

9 2

0 0 1 1 0 0 1 1 0

0 0 1 0 0 0 1 0 0

 

이동할 때 다른 경로의 이동을 방해(?)하기 때문이다.

만약 visit가 이차원 배열일 경우 위와 같은 경우는 -1이 나오게 된다.

말처럼 점프를 해서 먼저 좌표에 간뒤에, 인접 좌표로 먼저 visit을 할 경우에 다른 

좌표는 올 수 없다.

 

그래서 visit배열을 3차원으로 해야한다.

벽 부수고 이동하기 문제가 생각이 났다.

 

왜 visit를 3차원으로 생각해야하는지 잘 설명해주신 글이 있다.

https://www.acmicpc.net/board/view/30139

 

---

코드

package bfs_dfs;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int K, row, col;
    static int A[][];
    static boolean visit[][][];
    static int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1, 2, 2, -2, -2};
    static int dy[] = {0, 0, 1, -1, 2, -2, 2, -2, 1, -1, 1, -1};
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        Queue<Point> q = new ArrayDeque<>();
        q.offer(new Point(0, 0, 0, 0));
        visit[0][0][0] = true;
 
        while (!q.isEmpty()) {
            Point p = q.poll();
 
            if(p.x == row - 1 && p.y == col - 1){
                System.out.println(p.cnt);
                return;
            }
 
            for (int i = 0; i < 12; i++) {
                int X = p.x + dx[i];
                int Y = p.y + dy[i];
 
                if(!isRangeTrue(X,Y)) continue;
                if(A[X][Y] == 1) continue;
 
                if (i >= 4) {
                    if (p.k < K && !visit[X][Y][p.k + 1]) {
                        q.offer(new Point(X, Y, p.cnt + 1, p.k + 1));
                        visit[X][Y][p.k + 1] = true;
                    } else continue;
                }
                else{
                    if (!visit[X][Y][p.k]) {
                        q.offer(new Point(X, Y, p.cnt+1, p.k));
                        visit[X][Y][p.k] = true;
                    }
                }
            }
        }
        System.out.println(-1);
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        K = atoi(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        col = atoi(st.nextToken());
        row = atoi(st.nextToken());
 
        A = new int[row][col];
        visit = new boolean[row][col][K + 1];
 
        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                A[i][j] = atoi(st.nextToken());
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
 
    static class Point{
        int x, y, cnt, k;
 
        public Point(int x, int y, int cnt, int k) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.k = k;
        }
    }
}