BJ G5 1600 말이 되고픈 원숭이

BJ G5 1600 말이 되고픈 원숭이

 

 

문제링크

http://www.acmicpc.net/problem/15683

15683번: 감시

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=nIMjj0TlBL0

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2020. 3. 13.
 * @see https://www.acmicpc.net/problem/1600
 * @mem 89340
 * @time 528
 * @caution
 * 최소한의 동선이므로 #bfs로 구해보자.
 * 이동 중 상태 변화 - 그 상태가 탐색에 영향을 주는 경우 이므로 역시 탐색 과정에서 관리가 필요하다.
 */
public class BJ_G5_1600_말이되고픈원숭이 {
    static int K, C, R;

    static int[][] map;

    // 정답~
    static int minMoveCnt;

    // 원숭이로 이동하는 방향
    static int[][] dirsM = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    // 말로 이동하는 방향
    static int[][] dirsH = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));
        StringTokenizer tokens = null;

        K = Integer.parseInt(input.readLine()); // 말이동 회수 0이상 30이하의 정수
        tokens = new StringTokenizer(input.readLine());
        C = Integer.parseInt(tokens.nextToken()); // 폭 1이상 200이하의 자연수
        R = Integer.parseInt(tokens.nextToken()); // 높이 1이상 200이하의 자연수

        map = new int[R][C];
        for (int r = 0; r < R; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 0; c < C; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }
        /*        System.out.println("맵 확인");
        for (int[] row : map) {
            System.out.println(Arrays.toString(row));
        }*/
        // 입력 완료

        minMoveCnt = Integer.MAX_VALUE;
        bfs();
        System.out.println(minMoveCnt == Integer.MAX_VALUE ? -1 : minMoveCnt);
    }

    static void bfs() {
        // 방문 여부를 체크할 visited
        // K는 회수이므로 +1 필요
        boolean[][][] visited = new boolean[R][C][K + 1];

        Queue<Monkey> q = new LinkedList<>();
        Monkey start = new Monkey(0, 0, 0, 0);
        q.offer(start);

        visited[0][0][0] = true;

        while (!q.isEmpty()) {
            Monkey front = q.poll();

            // 목적지에 도착했다면 처리
            if (front.row == R - 1 && front.col == C - 1) {
                minMoveCnt = front.depth;
                return;
            }
            // 자식 탐색 - 단순 사방 탐색이 아니라 사방탐색 + 가능하다면 8방 탐색
            // 원숭이처럼 이동해보기
            moveLikeMonkey(q, front, visited);
            // 가능하다면 말처럼 이동해보기
            if (front.horseMove < K) {
                moveLikeHorse(q, front, visited);
            }
        }
    }

    static void moveLikeMonkey(Queue<Monkey> q, Monkey front, boolean[][][] visited) {
        // 사방탐색으로 자식 찾기
        for (int d = 0; d < dirsM.length; d++) {
            int nr = front.row + dirsM[d][0];
            int nc = front.col + dirsM[d][1];

            // 영역 안에 있고 땅이면 방문 가능
            if (isIn(nr, nc) && map[nr][nc] == 0) {
                // 갈 수 있으면 기존 이력에 따라서 동작
                if (!visited[nr][nc][front.horseMove]) {
                    Monkey newMonkey = new Monkey(nr, nc, front.depth + 1, front.horseMove);
                    visited[nr][nc][front.horseMove] = true;
                    q.offer(newMonkey);
                }
            }
        }
    }

    static void moveLikeHorse(Queue<Monkey> q, Monkey front, boolean[][][] visited) {
        // 자식 찾기
        for (int d = 0; d < dirsH.length; d++) {
            int nr = front.row + dirsH[d][0];
            int nc = front.col + dirsH[d][1];

            if (isIn(nr, nc) && map[nr][nc] == 0) {
                // 그렇게 말로 이동했을 때의 이력 가져오기.
                int nk = front.horseMove + 1;
                if (!visited[nr][nc][nk]) {
                    Monkey newMonkey = new Monkey(nr, nc, front.depth + 1, nk);
                    visited[nr][nc][nk] = true;
                    q.offer(newMonkey);
                }
            }
        }
    }

    static boolean isIn(int row, int col) {
        return 0 <= row && row < R && 0 <= col && col < C;
    }

    static class Monkey {
        int row, col;
        int depth; // 이동 회수
        int horseMove; // 말로 이동한 회수: <= K

        public Monkey(int row, int col, int depth, int horseMove) {
            this.row = row;
            this.col = col;
            this.depth = depth;
            this.horseMove = horseMove;
        }
    }

    static String src = "1\r\n" +
                        "4 4\r\n" +
                        "0 0 0 0\r\n" +
                        "1 0 0 0\r\n" +
                        "0 0 1 0\r\n" +
                        "0 1 0 0";
}