[백준] 1600번 말이 되고픈 원숭이 문제 BFS로 풀어보기

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

문제의 입력, 출력, 더 자세한 instruction은 위 백준 링크에서 확인하고 오늘은 1600번 풀이법에 대해 알아보도록 하자.

---

대표적으로 BFS를 사용할 수 있는 문제이다.

2021.01.18 - [알고리즘] - [그래프의 탐색] DFS(깊이 우선 탐색), BFS(너비 우선탐색) 알아보기

[그래프의 탐색] DFS(깊이 우선 탐색), BFS(너비 우선탐색) 알아보기

BFS에 대해 익숙하지 않다면 위의 개념을 먼저 보고 오는 것을 추천한다.

---

BFS에 관한 전형적인 문제인데 하나 변형된 부분이 있다. 바로 k번만 특수하게 움직일 수 있다는 것이다. 우리는 그동안 BFS를 풀 때 2차원 배열을 사용하여 행의 좌표, 열의 좌표를 사용하였다. 하지만 이 경우에는 k번만 특수하게 움직일 수 있으니 그동안 얼만큼 움직였는지를 별도로 기록할 필요가 있다. 

 

따라서 이번에는 3차원 배열을 만들어야 한다. 그리고 이동할 수 있는 방향도 총 12가지로 늘어난다. 예전에는 4가지가 대부분이었는데 이번에는 k번 이하로 대각선 방향도 움직일 수 있는 자유가 주어진다.

 

그래서 이번에는 

static final int[] dx = {0,0,1,-1,-2,-1,1,2,2,1,-1,-2};
static final int[] dy = {1,-1,0,0,1,2,2,1,-1,-2,-2,-1};
static final int[] used = {0,0,0,0,1,1,1,1,1,1,1,1};

이런식으로 static 변수들을 가져온다. dx와 dy모두 이동할 수 있는 방향을 뜻하고 used 라는 배열은 대각선으로 이동할 경우에 k번 중에 1번을 쓰는 것이므로 이런 식으로 하나의 배열을 더 준비했다.

---

처음에는 모든 d 배열을 -1로 초기화를 한 뒤에 만약 해당 d 배열의 값이 -1이라면 아직 방문하지 않았다는 뜻이므로 +1을 해준다. 이 문제에서는 인자가 세개가 필요하다는 것을 알 수 있을 것이다. 대각선 방향으로 몇 번 움직였는지의 회수도 queue에 함께 넣어주고 이것이 문제에서 입력받은 횟수보다 작거나 같은지를 확인해주어야 한다. 

 

이후 이 문제의 답은 d[n-1][m-1][k] 에 있다고 생각하면 잘못된 것이다. 문제에서 분명히 k 이하라고 했기 때문에 우리는 k의 값을 0부터 k까지 모두 다 검사하면서 최소값을 찾아야 하는 것이다. 

 

import java.util.*;

public class Main{
     static final int[] dx = {0,0,1,-1,-2,-1,1,2,2,1,-1,-2};
    static final int[] dy = {1,-1,0,0,1,2,2,1,-1,-2,-2,-1};
    static final int[] used = {0,0,0,0,1,1,1,1,1,1,1,1};
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int l = sc.nextInt();
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] a = new int[n][m];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int[][][] d = new int[n][m][l+1];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                Arrays.fill(d[i][j],-1);
            }
        }
        Queue<Integer> q=new LinkedList<>();
        q.add(0); q.add(0); q.add(0);
        d[0][0][0]=0;
        while(!q.isEmpty()){
            int x=q.remove();
            int y=q.remove();
            int c=q.remove();
            for(int k=0; k<12; k++){
                int nx=x+dx[k];
                int ny=y+dy[k];
                int nc=c+used[k];
                if (nx>=0 && nx<n &&ny>=0 &&ny<m && nc<=l){
                    if (a[nx][ny]!=1){
                        if (d[nx][ny][nc]==-1){
                            d[nx][ny][nc]=d[x][y][c]+1;
                            q.add(nx);
                            q.add(ny);
                            q.add(nc);
                        }
                    }
                }
            }
        }
        int ans = -1;
        for (int i=0; i<=l; i++) {
            if (d[n-1][m-1][i] != -1){
                if (ans == -1 || ans > d[n-1][m-1][i]) {
                ans = d[n-1][m-1][i];
            }
            } 
            
        }
        System.out.print(ans);
    }
}

이렇게 변형문제가 있을 수 있으니 잘 연습해두자.