visited배열이 3차원인 bfs 최단경로 탐색 문제 (백준 1600번)

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

1600번: 말이 되고픈 원숭이

 

풀이를 위한 핵심

말 이동 횟수에 따른 방문처리를 해줘야 합니다.

 

보통 방문체크를 visited[][] 와 같이 2차원 배열로 진행하지만, 이렇게 하게되면 말로 이동한 지점에 visited가 true로 되어 그냥 이동이 더 이상 진행하지 못하는 경우가 생길 수 있습니다.

 

예를들어

 

(0,0)에서 bfs를 수행하면 (0,1) (1,0) (1,2)가 방문체크 되고 큐에 들어갑니다.

 

여기서 한 턴 더 bfs를 수행하면

큐에 (1,1)이 들어가게 됩니다.

(1,1)에서 (1,2)로 이동할 수 있어야 하지만, 이전에 말로 이동했던 (1,2) 가 방문처리 되어 있어 이동하지 못하게 됩니다. (아래 그림처럼)

 

따라서 visited[][][] 와 같이 3차원 배열을 활용해서 말 이동을 0번 사용한 경우의 방문처리, 말 이동을 1번 사용한 경우의 방문처리, 2번 .. 과 같이 해줘야 합니다.

 

 

배운점

bfs 활용 최단경로를 탐색 문제에서는 이동방법이 같은지 다른지에 따라 방문처리를 다르게 해줘야 한다는 걸 배울 수 있었던 문제였다. (이번 문제에서는 이동방법이 (상하좌우 그냥 이동, 말 이동)으로 두 가지)

 

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;

public class Main {

    static final int INF = (int)1e9;
    static int K;
    static int H,W; // H * W 배열
    static int[][] map;
    static boolean[][][] visited;
    static int[] dr = {-1,0,1,0,-2,-2,-1,-1,1,1,2,2};
    static int[] dc = {0,1,0,-1,-1,1,-2,2,-2,2,-1,1};
    static int ans;



    static void solve(){
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0,0,0}); // (행,열,말 이동횟수)
        visited[0][0][0] = true;

        int tmp = -1; // 이동 경로의 길이

        while(!q.isEmpty()){
            int size = q.size(); // bfs를 한 턴씩 수행 (큐의 사이즈 만큼)
            tmp+=1; // 이동경로 + 1

            for(int s=0;s<size;s++){ // bfs 한 턴씩 수행
                int[] cur = q.pollFirst();
                int cr = cur[0]; // 행
                int cc = cur[1]; // 열
                int kMv = cur[2]; // 말로 이동한 횟수

                if(cr==H-1 && cc==W-1){ // 목적지에 도달했으면 최단경로 (bfs이기 때문에)
                    ans = tmp;
                    return;
                }

                for(int d=0;d<4;d++){ // 그냥 이동
                    int nr = cr + dr[d];
                    int nc = cc + dc[d];
                    if(nr<0 || nr>=H) continue;
                    if(nc<0 || nc>=W) continue;
                    if(map[nr][nc]==1) continue;
                    if(visited[nr][nc][kMv]) continue;
                    visited[nr][nc][kMv]=true;
                    q.offer(new int[]{nr,nc,kMv});
                }

                if(kMv >= K) continue;
                for(int d=4;d<12;d++){ // 말로 이동
                    int nr = cr + dr[d];
                    int nc = cc + dc[d];
                    if(nr<0 || nr>=H) continue;
                    if(nc<0 || nc>=W) continue;
                    if(map[nr][nc]==1) continue;
                    if(visited[nr][nc][kMv+1]) continue; // 다음 말로 방문할 위치 확인
                    visited[nr][nc][kMv+1]=true;
                    q.offer(new int[]{nr,nc,kMv+1});
                }
            }

        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        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];
        ans = -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());
            }
        }

        solve();

        System.out.println(ans);

    }

}