백준 1600번 : 말이 되고픈 원숭이 풀이 ( Java ) - BFS

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

Solution

1. 이 문제는 백준 2206 번 : 벽 부수고 이동하기와 굉장히 유사한 문제이다. simju9397.tistory.com/11

백준 2206번 : 벽 부수고 이동하기 풀이(Java)

2. 아직 저 문제를 풀어보지 않았다면 먼저 풀어보시길 바란다.

3. 메모리 초과의 이유

처음에 나는, 200*200*30 정도이므로 괜찮지 않을까? 하는 생각에 이 문제를 3차원 배열로 풀지 않고 2차원 배열을 복사해서 풀어봤다.

private static void bfs(int sx, int sy, int sd, boolean[][] visited, int k) {
        if(sx == W-1 && sy == H-1) {
            ans = Math.min(ans, sd);
            return;
        }
        visited[sx][sy] = true;
        boolean[][] visited1 = clone(visited);
        boolean[][] visited2 = clone(visited);
        for(int i = 0 ; i < 4; i++) {
            int nx = sx + dx[i];
            int ny = sy + dy[i];
            if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
            if(visited1[nx][ny]) continue;
            visited1[nx][ny] = true;
            bfs(nx, ny, sd + 1, visited1, k);
        }
        if(k > 0 ) {
            for(int i = 0 ; i < 8; i++) {
                int mx = sx + kx[i];
                int my = sy + ky[i];
                if(mx < 0 || my < 0 || mx >= W || my >= H) continue;
                if(visited2[mx][my]) continue;
                visited2[mx][my] = true;
                bfs(mx, my, sd + 1, visited2, k-1);
            }
        }
    }

일반 상하좌우 이동을 하는 visited1 배열, 말처럼 이동하는 visited2 배열을 각각 visited 에서 복사해주고, 각각을 재귀로 넘겨주는 식으로 했다. 하지만 당연히 터졌다.

 

4. 이 문제의 핵심은, 방문처리를 하는 visited 배열을

• H * W 크기의 boolean 배열이
• K+1 개 만큼 있도록

3차원으로 만들어주는 것이다. 그럼 visited[x][y][k] 의 의미는, 말처럼 이동한 횟수가 k번일 때, (x,y)가 방문한 지점인지 로 생각하는 것이다.

 

평범하게 이동할 때는 visited[nx][ny][현재 k] 를 true 로 해주고,

말처럼 이동할 때는 visited[nx][ny][현재 k + 1] 을 true 로 해주면 될 것이다.

 

그럼 왜 K+1 개 만큼 만들어야 할까?

바로 K = 0 인 경우를 포함해야 하기 때문이다. 원숭이는 K회 만큼 말처럼 이동 가능하므로, 말처럼 움직이는 행위 없이(K = 0) 도착지에 도착할 수도 있을 것이고, 한 번이든 두 번이든 K회 이하로만 움직이면 된다는 것이다.

 

그럼 큐에 저장하기 위한 Node 의 필드 변수는 좌표 x,y 와 더불어, 얼마나 움직였는지를 나타내주는 depth, 그리고 지금까지 몇 번 만큼 말처럼 이동했는지를 나타내주는 k로 지정해주면 된다.

private static class Node {
        int x;
        int y;
        int depth;
        int k;

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

 Source Code

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

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int K, W, H, ans;
    private static int[][] map;
    private static int[] dx = {-1,1,0,0};
    private static int[] dy = {0,0,-1,1};
    private static int[] kx = {-2,-1,1,2,2,1,-1,-2};
    private static int[] ky = {1,2,2,1,-1,-2,-2,-1};

    private static class Node {
        int x;
        int y;
        int depth;
        int k;

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

    private static void input() throws IOException {
        K = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer wh = new StringTokenizer(bufferedReader.readLine());
        W = Integer.parseInt(wh.nextToken()); // 가로 길이
        H = Integer.parseInt(wh.nextToken()); // 세로 길이
        map = new int[H][W];
        for(int i = 0; i < H; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0;j < W; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        ans = Integer.MAX_VALUE;
    }

    private static void bfs(Node start, boolean[][][] visited) {
        Deque<Node> deque = new ArrayDeque<>();
        deque.offer(start);
        visited[start.x][start.y][0] = true;
        while (!deque.isEmpty()) {
            Node node = deque.poll();
            int sx = node.x;
            int sy = node.y;
            int sd = node.depth;
            int sk = node.k; // 지금까지 말처럼 움직인 횟수
            if(sx == H-1 && sy == W-1) {
                ans = Math.min(ans, sd);
            }
            for(int i = 0 ; i < 4; i++) { // 평소처럼 이동하는 경우
                int nx = sx + dx[i];
                int ny = sy + dy[i];
                if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
                if(sk > K || visited[nx][ny][sk] || map[nx][ny] == 1) continue;
                deque.offer(new Node(nx, ny, sd+1, sk));
                visited[nx][ny][sk] = true; // 평소대로 움직이므로 sk를 그대로
            }
            if(sk <= K-1) { // 말처럼 이동할 수 있는 경우
                for(int i = 0 ; i < 8; i++) { 
                    int nx = sx + kx[i];
                    int ny = sy + ky[i];
                    if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
                    if(visited[nx][ny][sk+1] || map[nx][ny] == 1) continue;
                    deque.offer(new Node(nx, ny, sd+1, sk + 1));
                    visited[nx][ny][sk+1] = true; // 한 번 말처럼 이동하므로 sk+1 번째를 바꾼다.
                }
            }

        }
    }

    private static void solve() throws IOException {
        bfs(new Node(0,0,0, 0), new boolean[H][W][K+1]);
        if(ans==Integer.MAX_VALUE) {
            bufferedWriter.write(-1 + "\n");
        } else {
            bufferedWriter.write(ans + "\n");
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedWriter.close();
        bufferedReader.close();
    }
}