말이 되고픈 원숭이

📍 문제 설명

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

1600번: 말이 되고픈 원숭이

 

💡 접근

k = 1일 때 처음부터 움직일 수도 있지만 인접한 방향으로만 이동하다가 중간에 말처럼 이동할 수도 있기 때문에 그 부분 때문에 3차원 배열을 사용했음

며칠전 문제에서 해당하는 위치를 바로 리턴안해줬더니 시간초과가 뜨는 문제가 있어서 이번엔 지점 찾으면 바로 리턴해주는 식으로 접근했는데, 이번 문제에서는 100%에서 틀렸습니다.가 떴다.

이 문제에서는 2갈래로 이동이 가능하다보니 각자에서 나오는 좌표가 최적이 아닌 케이스가 하나 존재하는듯하다.

 

👩‍💻 코드

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

public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[] hx = {-2,-2,-1,-1,1,1,2,2};
    static int[] hy = {-1,1,-2,2,-2,2,-1,1};
    static int[] arr;
    static int[][] board;
    static boolean[][][] visited;
    static int n, m, k, t, num, cnt, second;
    static ArrayList<Integer> list = new ArrayList<>();

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

        k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[m][n];
        visited = new boolean[m][n][k+1];
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        if(bfs(0,0)) System.out.println(second);
        else System.out.println(-1);

    }

    private static boolean bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        //second 이동 횟수, cnt 말처럼 움직인 횟수
        q.add(new Point(x, y, 0, k));
        visited[x][y][k] = true;

        while (!q.isEmpty()) {
            Point cp = q.poll();
            if(cp.x == m-1 && cp.y == n-1) {
                second = cp.second;
                return true;
            }
            int nx, ny;
            for(int i = 0; i < 4; i++) {
                nx = cp.x + dx[i];
                ny = cp.y + dy[i];
                if(nx<0 || ny<0 || nx>=m || ny>=n || visited[nx][ny][cp.cnt] || board[nx][ny]==1) continue;
                visited[nx][ny][cp.cnt] = true;
                q.offer(new Point(nx, ny, cp.second+1, cp.cnt));
            }

            if(cp.cnt > 0) {
                for(int i = 0; i < 8; i++) {
                    nx = cp.x + hx[i];
                    ny = cp.y + hy[i];
                    if(nx<0 || ny<0 || nx>=m || ny>=n || visited[nx][ny][cp.cnt-1] || board[nx][ny]==1) continue;
                    visited[nx][ny][cp.cnt-1] = true;
                    q.offer(new Point(nx, ny,cp.second+1, cp.cnt-1));
                }
            }
        }
        return false;
    }


    private static class Point {
        private int x;
        private int y;
        private int second;
        private int cnt;

        public Point(int x, int y, int second, int cnt) {
            this.x = x;
            this.y = y;
            this.second = second;
            this.cnt = cnt;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    ", second=" + second +
                    '}';
        }
    }
}