[BOJ] 1600. 말이 되고픈 원숭이(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand the problem

  2. Redefine the problem + abstract

  3. Create a solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

최소의 동작으로 목적지까지 도착해야해서 BFS로 풀어야 겠다고 접근했고,

priority Queue 로 문제를 해결하고 했는데, 풀리지 않았다...

적은 동작으로 해당 좌표에 왔다고해서 무조건 최적의 해인 경로가 아니기때문이다.

만약 특정 지점으로 말처럼 이동해서 1번만에 왔다고 하자.

하지만 최적의 해로는 그 특정 지점까지 인접한 칸으로 이동하여 3번만에 왔다.

test case로 보자면 대충 아래와 같을 것 같다.

1

5 5

0 0 0 0 0

0 0 0 0 0

0 0 0 1 1

0 0 0 1 0

총 K번만 말처럼 움직이고, 그 외에는 그냥 인접한 칸(대각선 제외)으로만 이동한다.

K번 뛴 상태에서의 이동을 경로를 따로 관리해주어야 하므로 K개만큼의 map 배열을 사용하였다.

#. Code

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ1600 {       static int K, W, H, map[][];     static int[][][] dist;     static int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };     static int[] hx = {-1, -2, -1, -2, 1, 2, 1, 2}, hy = {-2, -1, 2, 1, -2, -1, 2, 1};       static class Info {         int x, y, k, cnt;           public Info(int x, int y, int k, int cnt) {             this.x = x;             this.y = y;             this.k = k;             this.cnt = cnt;         }             }       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;           K = Integer.parseInt(br.readLine()); // 말처럼 이동할 수 있는 횟수         st = new StringTokenizer(br.readLine(), " ");         W = Integer.parseInt(st.nextToken()); // 가로         H = Integer.parseInt(st.nextToken()); // 세로         map = new int[H][W];         dist = new int[H][W][K+1];                  for (int i = 0; i < H; i++) {             st = new StringTokenizer(br.readLine(), " ");             for (int j = 0; j < W; j++) {                 map[i][j] = Integer.parseInt(st.nextToken());             }         }                  int res = -1;         Queue<Info> q = new LinkedList<>();         // (0,0)에서 시작.         q.add(new Info(0,0,0,0));         dist[0][0][0] = 0;         while(!q.isEmpty()) {             Info now = q.poll();             // 도착지에 도착했다면              if(now.x == H-1 && now.y == W-1) {                 res = dist[now.x][now.y][now.k];                 break;             }                          // 총 K번만 말처럼 움직이고, 그 외에는 그냥 인접한 칸(대각선 제외)으로만 이동             // 말처럼 이동할 수 있는 횟수가 남았다면             if(now.k < K) {                 // 말처럼 이동해보자.                 for (int h = 0; h < 8; h++) {                     int xx = now.x + hx[h];                     int yy = now.y + hy[h];                     if(!shallGo(xx, yy, now.k + 1)) continue;                     // 이동할 수 있는 칸이면                     dist[xx][yy][now.k + 1 ] = now.cnt + 1;                     q.add(new Info(xx, yy, now.k + 1, now.cnt + 1));                 }             }             // 인접한 칸으로 이동             for (int d = 0; d < 4; d++) {                 int xx = now.x + dx[d];                 int yy = now.y + dy[d];                 if(!shallGo(xx, yy, now.k)) continue;                 // 이동할 수 있는 칸이면                 dist[xx][yy][now.k] = now.cnt + 1;                 q.add(new Info(xx, yy, now.k, now.cnt + 1));             }                  }         System.out.println(res);     }          public static boolean shallGo(int x, int y, int k) {         // 범위를 벗어나면 pass         if(x < 0 || y < 0 || x >= H || y >= W) return false;         // 벽이면 pass         if(map[x][y] == 1) return false;         // 이미 방문한 곳이면 pass         if(dist[x][y][k] != 0) return false;                  return true;     } } Colored by Color Scripter

cs

line 49) (0, 0)부터, 말처럼 0번 이동, 0번 동작, 으로 시작

line 60~70) 말처럼 이동

line 72~79) 평범하게 인접한 칸으로 이동

* 돌아보니 딱히 설명한 부분이 없을 정도로.. 그냥 기본적인 너비 우선 탐색문제다.

  다만 조금 더 신경 써주어야 할 부분은 

  `최소의 동작`으로 이동한 칸이라고 무조건 `최적의 경로`가 아니라는 것.

  또, K에 따른 visit 처리를 해주어야 한다는 것.

  뽑자면 이정도인 것 같다.

#. Code_v2

 

문제를 다시 풀어보았을 때는 더 깔끔하게 풀 수 있었다.

visited 배열도 2차원 배열로 해결해보려고 했는데,

말이 먼저 멀리 뛰어가버리는 경우가 있어서 안되는것 같다ㅠ_ㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ1600_v2 {
 
    static int K, W, H, res = -1, map[][];
    static boolean[][][] visited;
    static int[] dx = { 1, 0, -1, 0, -1, -2, -2, -1, 1, 2, 1, 2 };
    static int[] dy = { 0, 1, 0, -1, -2, -1, 1, 2, -2, -1, 2, 1 };
 
    static class State {
        // x좌표, y좌표, 이동 거리, 말처럼 뛴 횟수
        int x,y,dist,jump;
 
        public State(int x, int y, int dist, int jump) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.jump = jump;
        }
        
    }
    
    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());
        W = Integer.parseInt(st.nextToken());    // 가로
        H = Integer.parseInt(st.nextToken());    // 세로
        map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        Queue<State> q = new LinkedList<>();
        visited[0][0][0] = true;
        q.add(new State(0, 0, 0, 0));
        while(!q.isEmpty()) {
            State now = q.poll();
            // 도착지에 도달
            if(now.x == H-1 && now.y == W-1) {
                res = now.dist;
                break;
            }
            
            // 말처럼 뛸 수 있는지 확인
            int animal = now.jump >= K ? 4 : 12;
            // 이동해보자
            for (int d = 0; d < animal; d++) {
                int xx = now.x + dx[d];
                int yy = now.y + dy[d];
                
                // 범위 초과 시 pass
                if(xx < 0 || yy < 0 || xx >= H || yy >= W) continue;
                // 장애물이 있을 경우 pass
                if(map[xx][yy] == 1) continue;
                // 원숭이처럼 이동할 경우
                if(d < 4) {
                    // 이미 왔던 곳이라면
                    if(visited[xx][yy][now.jump]) continue;
                    visited[xx][yy][now.jump] = true;
                    q.add(new State(xx, yy, now.dist + 1, now.jump));
                }
                // 말처럼 이동할 경우
                else {
                    if(visited[xx][yy][now.jump + 1]) continue;
                    visited[xx][yy][now.jump + 1] = true;
                    q.add(new State(xx, yy, now.dist + 1, now.jump + 1));
                }
            }
        }
        
        System.out.println(res);
    }
}
 

참고) N방 탐색 시 코드 중복을 줄이기 위해 아래와 같이 해결할 수 있겠구나..

// 현재 상태의 k가 K를 넘지 않는다면 12방 아니라면 4방에 대해서
for(int d = 0; d < ( s.k < K ? 12 : 4) ; d++) {
    int nr = s.r + dr[d];
    int nc = s.c + dc[d];
    int nk = ( d >=  4 ? s.k + 1 : s.k);//말처럼 뛸때는 k가 증가
    int ncnt = s.cnt + 1;
    // 밖으로 나가면 아웃
    if( nr < 0 || nc < 0 || nr >= H || nc >= W)
        continue;
    // 장애물이거나. 아웃
    if( map[nr][nc] == 1 )
        continue;
    //같은 k회로 방문한적이 있으면 아웃
    if( visited[nr][nc][nk] )
        continue;
    // 해당 위치 해당 k회에 대해서 방문체크하고
    visited[nr][nc][nk] = true;
    // 해당 위치 해당 k회에 이동횟수+1 상태를 큐에 삽입
    queue.add(new Status(nr, nc, nk, ncnt));
}