[백준] 말이 되고픈 원숭이 1600 java - bfs

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

 

처음에 말의 이동이 잘 이해가 가지 않아서 어려웠고

두 번째 난관은 같은 위치에 있을 때에도

k를 쓴 갯수에 따라서 다른 경우로 봐야하는데, 이를 간과해서 어려웠다 !

 

 

틀린 코드

import java.io._;  
import java.util._;

public class Main {  
static int K, W, H;  
static int\[\]\[\] graph;  
static boolean\[\]\[\] visited;  
static int\[\] dx1 = {0,0,1,-1};  
static int\[\] dy1 = {1,-1,0,0};  
static int\[\] dx2 = {2,2,1,1,-2,-2,-1,-1};  
static int\[\] dy2 = {1,-1,2,-2,1,-1,2,-2};
static int bfs(int x, int y){
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{x,y,0,0});
    visited[x][y] = true;

    while(!q.isEmpty()){
        int[] now = q.poll();
        int nowX = now[0];
        int nowY = now[1];
        int cnt = now[2];
        int kCnt = now[3];

        if(nowX==H-1 && nowY==W-1){
            return cnt;
        }

        if(kCnt<K){
            for(int i=0;i<8;i++){
                int nextX = nowX+dx2[i];
                int nextY = nowY+dy2[i];
                if(nextX>=0&&nextX<H && nextY>=0&&nextY<W){
                    if(!visited[nextX][nextY] && graph[nextX][nextY]==0){
                        q.add(new int[]{nextX, nextY, cnt+1, kCnt+1});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        } else {
            for(int i=0;i<4;i++){
                int nextX = nowX+dx1[i];
                int nextY = nowY+dy1[i];
                if(nextX>=0&&nextX<H && nextY>=0&&nextY<W){
                    if(!visited[nextX][nextY] && graph[nextX][nextY]==0){
                        q.add(new int[]{nextX, nextY, cnt+1, kCnt});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }
    return -1;
}

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = null;

    K = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine());
    W = Integer.parseInt(st.nextToken());
    H = Integer.parseInt(st.nextToken());

    graph = new int[H][W];
    visited = new boolean[H][W];

    for(int i=0;i<H;i++){
        st = new StringTokenizer(br.readLine());
        for(int j=0;j<W;j++){
            graph[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    System.out.println(bfs(0,0));

}

 

반례

1

5 5

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 1 1

0 0 0 1 0

-> 6이 답인데 위의 코드로 하면 -1이 출력..

같은 위치에 있는 경우도 말로 이동한 것인지 아닌지에 따라서

다르게 봐야 함 !!!

 

정답 코드

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

public class Main {
    static int K, W, H;
    static int[][] graph;
    static boolean[][][] visited;
    static int[] dx1 = {0,0,1,-1};
    static int[] dy1 = {1,-1,0,0};
    static int[] dx2 = {2,2,1,1,-2,-2,-1,-1};
    static int[] dy2 = {1,-1,2,-2,1,-1,2,-2};

    static int bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y,0,0});
        visited[x][y][0] = true;

        while(!q.isEmpty()){
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];
            int cnt = now[2];
            int kCnt = now[3];

            if(nowX==H-1 && nowY==W-1){
                return cnt;
            }

            for(int i=0;i<4;i++){
                int nextX = nowX+dx1[i];
                int nextY = nowY+dy1[i];
                if(nextX>=0&&nextX<H && nextY>=0&&nextY<W){
                    if(!visited[nextX][nextY][kCnt] && graph[nextX][nextY]==0){
                        q.add(new int[]{nextX, nextY, cnt+1, kCnt});
                        visited[nextX][nextY][kCnt] = true;
                    }
                }
            }

            if(kCnt<K){
                for(int i=0;i<8;i++){
                    int nextX = nowX+dx2[i];
                    int nextY = nowY+dy2[i];
                    if(nextX>=0&&nextX<H && nextY>=0&&nextY<W){
                        if(!visited[nextX][nextY][kCnt+1] && graph[nextX][nextY]==0){
                            q.add(new int[]{nextX, nextY, cnt+1, kCnt+1});
                            visited[nextX][nextY][kCnt+1] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        K = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        graph = new int[H][W];
        visited = new boolean[H][W][K+1];

        for(int i=0;i<H;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<W;j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(bfs(0,0));

    }

}