[문제]
출처 - https://www.acmicpc.net/problem/16933
16933번: 벽 부수고 이동하기 3
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
[문제 풀이]
골드 1의 난이도를 가졌지만 벽 부수고 이동하기 와 벽 부수고 이동하기2 를 해결했다면 이 문제도 해결할 수 있다!
K개를 부실 수 있는 조건과 낮과 밤이라는 조건이 생겼다.
이동을 하거나 이동하지 않고 같은 칸에 머물러도 낮과 밤은 바뀐다. (이동하지 않아도 방문한 칸의 개수가 늘어나는것으로 처리) 벽을 부수고 이동하는 것이 경로가 더 빠르면 벽을 K개 부수고 이동할 수 있다. 단, 벽은 낮에만 부술 수 있다.
- BFS 사용
- Queue에 X좌표, Y좌표, 거리정보, 벽을 부순 상태 정보, 낮과밤 추가하여 탐색
- 방문처리는 visit[x][y][현재벽을부순개수][낮과밤] 으로 처리
- 벽을 만났을 때 벽을 부신 횟수가 K미만 이어야만 벽을 부실 수 있다. 단! 낮이여야만 한다
- 이동하지 않을때 낮과 밤은 바뀌고 거리정보는 +1이 되어야한다. (문제의 조건에 적혀있음)
- N, M 에 도달했을 때 종료 그때의 거리 값을 정답으로 출력
- 탐색이 끝나도 N, M에 도달하지 못할 경우에는 -1 출력 (0, 0 에서 시작했기 때문에 N-1, M-1 에서 종료)
[소스 코드]
import java.io.*;
import java.util.*;
class Node{
int x,y,dist,boom,day;
Node(int x, int y, int dist, int boom, int day){
this.x = x;
this.y = y;
this.dist = dist;
this.boom = boom;
this.day = day;
}
}
public class Main {
static final int dx[] = {0,0,1,-1};
static final int dy[] = {1,-1,0,0};
static int map[][];
static boolean visit[][][][];
static int n,m,k,ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
map = new int[n][m];
visit = new boolean[n][m][k+1][2];
for(int i=0; i<n; i++) {
String s = br.readLine();
for(int j=0; j<m; j++) {
map[i][j] = s.charAt(j) - '0';
}
}
ans = -1;
bfs();
System.out.println(ans);
}
static void bfs() {
Queue<Node> q = new LinkedList<>();
q.add(new Node(0,0,1,0,0)); //x, y, dist, boom, day
visit[0][0][0][0] = true;
while(!q.isEmpty()) {
Node now = q.poll();
int x = now.x;
int y = now.y;
if(x == n-1 && y == m-1) {
ans = now.dist;
return;
}
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(0 > nx || nx >= n || 0 > ny || ny >= m) continue;
if(map[nx][ny] == 0) {
if(now.day == 0 && !visit[nx][ny][now.boom][now.day+1]) {
q.add(new Node(nx,ny,now.dist+1,now.boom,now.day+1));
visit[nx][ny][now.boom][now.day+1] = true;
}
else if(now.day == 1 && !visit[nx][ny][now.boom][now.day-1]){
q.add(new Node(nx,ny,now.dist+1,now.boom,now.day-1));
visit[nx][ny][now.boom][now.day-1] = true;
}
}else { //낮은 0 밤은 1
if(now.boom < k && now.day == 0 && !visit[nx][ny][now.boom+1][now.day+1]) {
visit[nx][ny][now.boom+1][now.day+1] = true;
q.add(new Node(nx,ny,now.dist+1,now.boom+1,now.day+1));
}else if(now.boom < k && now.day == 1 && !visit[x][y][now.boom][now.day-1]) {
visit[x][y][now.boom][now.day-1] = true;
q.add(new Node(x,y,now.dist+1,now.boom,now.day-1));
}
}
}
}
}
}