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

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

1600번: 말이 되고픈 원숭이

풀이

기본적인 bfs 에서 말이 이동할 수 있는 경로만 신경써주면 된다.

말처럼 이동할 수 있는 기회는 K번으로 횟수가 제한되어있으며 벽을 넘을 수 있다.

 

시작점 (0, 0) 으로 출발해서 (w, h) 까지 최소한의 횟수로 도착하면 된다.

원숭이 상태와 말 상태일 때를 구분해서 돌려주면 쉽게 해결할 수 있다.

 

1. 원숭이 상태일 경우

  1) 이미 방문을 했는지 여부 판단 (visited[nx][ny][0])

 

2. 말 상태일 경우

  1) 말 상태를 몇 번 사용했는지 여부 (now.horse < K)

  2) 이미 방문을 했는지 여부 판단 (visited[nx][ny][now.horse])

// 원숭이
for (int i=0; i<4; i++) {
    int nx = now.x + dx[i];
    int ny = now.y + dy[i];
				
    if (nx < 0 || nx >= h || ny < 0 || ny >= w || visited[nx][ny][now.horse] || map[nx][ny] == 1) continue;
				
    q.add(new Position(nx, ny, now.cnt+1, now.horse));
    visited[nx][ny][now.horse] = true;
}

// 말
if (now.horse < K) {
    for (int i=0; i<8; i++) {
        int nx = now.x + hdx[i];
        int ny = now.y + hdy[i];
					
        if (nx < 0 || nx >= h || ny < 0 || ny >= w || visited[nx][ny][now.horse+1] || map[nx][ny] == 1) continue;
					
        q.add(new Position(nx, ny, now.cnt+1, now.horse+1));
        visited[nx][ny][now.horse+1] = true;
    }
}

방문 여부를 체크하는 visited 배열도 두 가지로 나누어주면 된다. 말 상태를 모두 사용했을 때와 모두 사용하지 않았을 때로 구분해서 bfs를 돌려주면 된다. 

 

종료 시점은 도착 지점 (w, h) 에 가장 먼저 도달한 경우이다.

 

 

<최종코드>

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

public class Main {
    static int[] hdx = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] hdy = {-1, 1, -2, 2, -2, 2, -1, 1};
    static int[] dx = {0, 1, 0 ,-1};
    static int[] dy = {1, 0, -1, 0};
    static int K, w, h;
    static boolean[][][] visited;
    static int[][] map;
    
    public static class Position {
        int x;
        int y;
        int cnt;
        int horse;
		
        public Position(int x, int y, int cnt, int horse) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.horse = horse;
        }
    }
	
    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];
        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());
            }
        }
		
        int ans = bfs();
        System.out.println(ans);
    }
	
    public static int bfs() {
        Queue<Position> q = new LinkedList<>();
        q.add(new Position(0, 0, 0, 0));
        visited[0][0][0] = true;
		
        while (!q.isEmpty()) {
            Position now = q.poll();
			
            if (now.x == h-1 && now.y == w-1) {
                return now.cnt;
            }
			
            // 원숭이
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
				
                if (nx < 0 || nx >= h || ny < 0 || ny >= w || visited[nx][ny][now.horse] || map[nx][ny] == 1) continue;
				
                q.add(new Position(nx, ny, now.cnt+1, now.horse));
                visited[nx][ny][now.horse] = true;
            }
			
            if (now.horse < K) {
                for (int i=0; i<8; i++) {
                    int nx = now.x + hdx[i];
                    int ny = now.y + hdy[i];
					
                    if (nx < 0 || nx >= h || ny < 0 || ny >= w || visited[nx][ny][now.horse+1] || map[nx][ny] == 1) continue;
					
                    q.add(new Position(nx, ny, now.cnt+1, now.horse+1));
                    visited[nx][ny][now.horse+1] = true;
                }
            }
        }
		
        return -1;
    }
}

내가 생각한 시간 복잡도: 실행된 bfs 횟수는 1번 = O(V+E)

V : 가로 x 세로

E : 한 정점의 간선 (원숭이 : 4개, 말 : 8개) = 12V

따라서, V + 12V = 13V => O(13wh)