[문제] 벽 부수고 이동하기

문제

소스코드

import java.util.*;

class Pair2{
	int x;
	int y;
	boolean c ; // 부쉈다면 ture, 부수지 않았다면 false
	
	Pair2(int x, int y, boolean c){
		this.x = x;
		this.y = y;
		this.c = c;
	}
}
public class Maze2 {
	public static final int[] dx = {0,0,1,-1};
	public static final int[] dy = {1,-1,0,0};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] input = sc.nextLine().split(" ");
		int n = Integer.parseInt(input[0]); 
		int m = Integer.parseInt(input[1]); 
		
		int[][] map = new int[n][m];
		for(int i=0; i<n; i++){
			String[] line = sc.nextLine().split(" ");
			for(int j=0; j<m; j++){
				map[i][j] = Integer.parseInt(line[j]);
			}
		}
		int[][] dist = new int[n][m]; // 거리
		boolean[][] check = new boolean[n][m]; // 벽을 부수지 않은 차원
		boolean[][] check2 = new boolean[n][m]; // 벽을 부순 후의 차원
		
		Queue<Pair2> q = new LinkedList<Pair2>(); //bfs
		q.add(new Pair2(n-1, 0, false));
		check[n-1][0] = true;
		dist[n-1][0] = 0;
		
		while(!q.isEmpty()){
			if(dist[0][m-1] != 0){ // 지점에 도착했다면 while문을 멈춤
				break;
			}
			Pair2 p = q.remove();
			int x = p.x;
			int y = p.y;
			boolean c = p.c;
			for(int k=0; k<4; k++){
				int nx = x+dx[k];
				int ny = y+dy[k];
				if(0<=nx && nx<n && 0<=ny && ny<m){ // 길이 있을 경우
					if(c == true){ // 벽을 이미 1번 부쉈을 경우
						if(check[nx][ny] == false && check2[nx][ny] == false  && map[nx][ny] == 0){
							q.add(new Pair2(nx, ny, c)); // 벽을 이미 부쉈기 때문에 그대로 
							dist[nx][ny] = dist[x][y] + 1; // 거리를 1 더해줌
							check2[nx][ny] = true; // 벽을 부순 후의 차원에 갔던 길을 true로 표시					
						}
					}
					else{ // 벽을 부순 적이 없을 경우
						if(check[nx][ny] == false){ // 가지 않았던 길일 경우
							if(map[nx][ny] == 0){ // 벽이 없는 경우
								q.add(new Pair2(nx, ny, c)); // 벽을 수지 않았기 때문에 그대로 
							}
							if(map[nx][ny] ==1){ // 벽이 있는 경우
								q.add(new Pair2(nx, ny, true)); // 벽을 부쉈기 때문에 true
							}
							dist[nx][ny] = dist[x][y] + 1; // 거리를 1 더해줌
							check[nx][ny] = true; // 갔던 길을 true로 표시
						}
					}
				}
			}
		}
		System.out.println(dist[0][m-1]);
	}
}

풀이

미로 찾기 문제와 동일한 방식으로 풀었지만 벽을 한 번 부술 수 있기 때문에 조금 더 생각이 필요한 문제였다. 

1. 벽 부수기를 사용한 경우 c == true

2. 벽 부수기를 사용하지 않은 경우 c == false

1. 벽을 부순 후에 차원 check2[]

2. 벽을 부수지 않은 차원 check[]

가장 먼저 벽을 부수기를 사용했는지 안했는지를 알기 위해 기존의 미로 찾기보다 Pair2에 c를 사용하여 표시를 할 수 있도록 해두었다. 다음 중요한 개념은 지나온 길을 알려주는 check[] 배열을 2개를 만들어서 차원을 2개로 나누었다. 벽을 부수지 않았을 때는 check[]에 지나온 길을 표시하고, 벽을 부순 후부터는 check2[]에 지나온 길을 표시하여 벽을 부순 후에 차원이 벽을 부수지 않은 차원에 영향을 미치지 못하도록 하였다.