[백준/JAVA] 1600번: 말이 되고픈 원숭이

📖 문제

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

 

 

 

💡  풀이 방식

• BFS

필요 자료구조
- 상하좌우 이동을 위한 4방향 배열 dx,dy
- 말인 경우 대각선 8방향 이동을 위한 배열 hx, hy
- 격자판 정보 저장할 2차원 int형 배열
- 해당 좌표에서 방문 여부와 말 이동찬스 사용 횟수를 저장하는 3차원 boolean형 배열 ⇒ chk[세로][가로][말 이동찬스 사용 횟수]

 

 

1. 정수 K를 입력받는다.

2. 가로 W와 세로 H를 입력받는다.

3. 크기가 H*W 인 격자판의 정보를 입력받는다.

4. 맨 왼쪽 위부터 맨 오른쪽 아래까지 최단 거리로 간다고 했으므로 맨 왼쪽 위에 있는 (0, 0)부터 BFS를 수행한다.

  - 2차원 배열의 좌표 내 방문 여부 뿐만 아니라, 매 탐색마다 말 이동 찬스를 사용했는지 확인해야 하므로 3차원 배열을 활용한다.

  4-1. 현재 위치에서 원숭이의 이동 방법으로 4방향 탐색한다.

  4-2. 현재 위치에서 말 이동찬스 K가 남아있다면, 말 이동 방법으로 8방향 탐색한다.

  4-3. 현재 위치가 맨 오른쪽 아래 점이라면, 현재까지 이동한 거리를 리턴하고 탐색을 종료한다.

 

5. 모든 탐색이 끝나고 현재까지 이동한 거리를 리턴할 수 없다면, 탐색이 불가한 것이므로 -1을 출력한다.

 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    
    // 말인 경우 대각선 8방향 이동
    static int[] hx = {1,2,2,1,-1,-2,-2,-1};
    static int[] hy = {2,1,-1,-2,-2,-1,1,2};
    
    static int K,W,H;
    static int[][] map;
    static boolean[][][] chk;
    
    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];
        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());
            }
        }
        
        chk = new boolean[H][W][K+1];    // 세로, 가로, 말 이동찬스 사용 횟수
        System.out.println(bfs());
    }
    
    private static int bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0,0,0,0});
        
        chk[0][0][0] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            int px = now[0];
            int py = now[1];
            int chance = now[2];
            int move = now[3];
            
            // 맨 오른쪽 아래 도착하면 종료
            if(px == W-1 && py == H-1) {
                return move;
            }
            
            // 1. 원숭이 이동 - 4방향 탐색
            for(int d = 0 ; d < 4 ; d++) {
                int nx = px + dx[d];
                int ny = py + dy[d];
                
                // 격자 범위 벗어나거나, 이미 방문한 적 있는 칸이면 pass
                if(nx < 0 || nx > W-1 || ny < 0 || ny > H-1)    continue;
                if(chk[ny][nx][chance]) continue;
                
                if(map[ny][nx] != 1) {
                    chk[ny][nx][chance] = true;
                    q.add(new int[] {nx, ny, chance, move + 1});
                }
            }
            
            // 2. 말 찬스 이동 - 찬스 남아있으면 말 8방향 탐색
            if(chance < K) {
                for(int d = 0 ; d < 8 ; d++) {
                    int nx = px + hx[d];
                    int ny = py + hy[d];
                    
                    // 격자 범위 벗어나거나, 이미 방문한 적 있는 칸이면 pass
                    if(nx < 0 || nx > W-1 || ny < 0 || ny > H-1)    continue;
                    if(chk[ny][nx][chance + 1]) continue;
                    
                    if(map[ny][nx] != 1) {
                        chk[ny][nx][chance + 1] = true;
                        q.add(new int[] {nx, ny, chance + 1, move + 1});
                    }
                }
            }
        }
        
        return -1;
    }
}

 

 

 

➕ 다른 풀이

3차원 방문 배열에서 행과 열을 뒤집지 않고 푼 풀이 ! 다음엔 이렇게 풀어보겠다..

[백준] 1600: 말이 되고픈 원숭이(Java)

---

💦 어려웠던 점

- 3차원 방문 배열을 사용할 생각을 하지 못 했다.

 

 

 

🧐 새로 알게 된 내용

- 매 탐색마다 말 이동찬스 썼는지 확인하기 위해 3차원 배열을 사용하는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BOJ] 백준 1600번 말이 되고픈 원숭이 (Java)