[백준] 1600번 말이 되고픈 원숭이 문제 BFS로 풀어보기
1. 문제
문제의 입력, 출력, 더 자세한 instruction은 위 백준 링크에서 확인하고 오늘은 1600번 풀이법에 대해 알아보도록 하자.
2. BFS 개념
대표적으로 BFS를 사용할 수 있는 문제이다.
https://www.programmingstory.com/2024/02/dfs-bfs.html
BFS에 대해 익숙하지 않다면 위의 개념을 먼저 보고 오는 것을 추천한다.
3. 풀이
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까지 모두 다 검사하면서 최소값을 찾아야 하는 것이다.
3. 코드
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);
}
}이렇게 변형문제가 있을 수 있으니 잘 연습해두자.
.png)
.png)
.png)
.png)