[BOJ]1600번 : 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

 

분류 : BFS

import java.io.*;
import java.util.*;

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {

    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    public static MyScanner sc = new MyScanner();
    static int[] Hx = {-2,-1,1,2,2,1,-1,-2};
    static int[] Hy = {-1,-2,-2,-1,1,2,2,1};
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    static int K,W,H,map[][];
    static boolean[][][] visited;
    public static void main(String[] args) throws IOException {
        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[201][201][31];
        int ans = BFS();
        out.println(ans);
        out.flush();
    }
    private static int BFS() {
        
        Queue<Point> q = new LinkedList<Point>();
        visited[0][0][K]=true;
        q.offer(new Point(0,0,K));
        int depth=0;
        while(!q.isEmpty())
        {
            int size = q.size();
            for(int sz =0;sz<size;sz++)
            {
                Point p = q.poll();
                int x = p.x;
                int y = p.y;
                int move = p.move;
                if(x == H-1 && y == W-1){
                    return depth;
                }
                if(move>0){
                for(int h=0;h<8;h++)
                {
                    int Hx1 = x+Hx[h];
                    int Hy1 = y+Hy[h];
                    if(Hx1<0 || Hy1<0 || Hx1>=H || Hy1>=W) continue;                    
                        if(map[Hx1][Hy1]==0  && !visited[Hx1][Hy1][move-1])
                        {
                            visited[Hx1][Hy1][move-1]=true;
                            q.offer(new Point(Hx1,Hy1,move-1));
                        }
                }
                }
                for(int M =0;M<4;M++){
                    int Mx1 = x+dx[M];
                    int My1 = y+dy[M];
                    if(Mx1<0 || My1<0 || Mx1>=H || My1>=W) continue;
                    if(map[Mx1][My1]==0 && !visited[Mx1][My1][move]){
                        visited[Mx1][My1][move]=true;
                    q.offer(new Point(Mx1,My1,move));
                    }
                    }
            }
            depth++;
        }
        return -1;
    }
}
class Point{
    int x,y,move;
    Point(int x, int y , int move){
        this.x = x;
        this.y = y;
        this.move = move;
    }
}

 

BFS 문제이고 나이트의 이동 문제와 비슷해 보여서 쉽게 풀릴 줄 알았다.

계속 틀리길래 뭐지.. 하고서 봤더니 가로,길이 입력의 순서가 바뀌어서 계속 고민했다...

그러다 질문 검색에 있는 많은 반례도 집어 넣는데 이상하게 케이스 하나가 안돼서 멘붕...

그러다 문제점을 발견했고 해결 완료.. 문제를 제대로 읽읍시다