[BOJ-JAVA] 2206 : 벽 부수고 이동하기

문제

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

2206번: 벽 부수고 이동하기

 

문제에 대해 간략하게 설명해보자면

• 이동할 수 있는 위치 0과 벽으로 막힌 위치 1로 만들어진 N*M 크기의 맵에서
• (1,1)에서 출발해 (N,M)에 도착하는 최단 경로를 구해야 한다
• 중요한 점은
  • 한 칸에서 이동할 수 있는 곳은 상하좌우이며
  • 최단 경로는 시작과 도착 칸을 포함한 칸의 개수 기준
  • 이때, 경로상에서 딱 한번 벽을 부수고 지나갈 수 있음

 

문제풀이

💡 초기 접근 방법

일단 최단 경로는 구해야 한다는 점에서 BFS 알고리즘을 사용해야함을 알 수 있었다.

• BFS 알고리즘이란 너비우선탐색 알고리즘으로 가까운 곳에 대해 차례로 탐색하는 알고리즘을 말한다.

 

Queue를 사용해 BFS를 구현하고 이때 visited 배열을 두어 방문에 대한 처리를 하도록 했다.

여기서 말하는 방문처리란!

• 모든 경로를 탐색하는 것은 비효율적이기 때문에
• 이미 탐색을 한곳에 대해서는 표시를 해두어
• 다시 탐색하지 않는 방법을 말한다.

 

방문처리와 함께 최단 경로를 구해야하기 때문에 각 위치에 도달했을 때의 최단 경로를 visited 배열에 저장하도록 했다.

결론적으로 visited 배열을 방문 여부와 최단 경로 값을 모두 나타낸다.

• int형 배열
• 0 : 방문 안함
• 1~ : 해당 위치까지의 최단 경로 

 

문제의 조건에서 벽을 한번 뿌술 수 있다고 했기 때문에 탐색 시에 각 위치에서 "벽을 이미  뿌쉈는지에 대한 여부"를 알 수 있어야 했다. 따라서 위치 정보를 담는 객체인 Location 클래스를 정의해 정보를 담았다. 

class Location {
	int row;
    int col;
    int isBreak; // 벽 부순 여부 - 0: 안부숨 1: 부숨
    
    public Location(int row, int col, int isBreak){
    	row = row;
        col = col;
        isBreak = isBreak;
    }
}

 

다음의 방식으로 작성한 코드는 다음과 같았다. (틀린코드에요..)

public class Main {
	
	private static int N, M;
	private static int[][] map;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split(" ");
		N = Integer.parseInt(line[0]);
		M = Integer.parseInt(line[1]);
		
		map = new int[N][M];
		
		for(int i=0; i<N; i++) {
			line = br.readLine().split("");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(line[j]);
			}
		}
		
		System.out.println(bfs(0, 0, N-1, M-1));
		
	}
	
	private static int bfs(int str_row, int str_col, int end_row, int end_col) {
		Queue<Location> queue = new ArrayDeque<Location>();
		queue.add(new Location(str_row, str_col, false));
		
		int[][] visited = new int[N][M];
		visited[str_row][str_col] = 1;
		
		int[] dr = {-1, 0, 1, 0};
		int[] dc = {0, 1, 0, -1};
		
		while(!queue.isEmpty()) {
			Location lo = queue.remove();
			if(lo.row == end_row && lo.col == end_col) {
				return visited[end_row][end_col];
			}
			
			for(int d=0; d<4; d++) {
				int r = lo.row + dr[d];
				int c = lo.col + dc[d];
				
				if(r < 0 || r >=N || c < 0 || c >= M) continue;
				
				// 방문하지 않았거나 더 짧은 경로 인 경우
				if(visited[r][c] == 0 || visited[r][c] >= visited[lo.row][lo.col]+1) {
					// 이동할 수 있을 경우
					if(map[r][c] == 0) {
						visited[r][c] = visited[lo.row][lo.col] +1;
						queue.add(new Location(r, c, lo.isBreak));
						continue;
					}
					
					// 벽일 경우 -> 아직 벽 뿌수기 안했다면
					if(!lo.isBreak) {
						visited[r][c] = visited[lo.row][lo.col] +1;
						queue.add(new Location(r, c, true));
					}
				}
			}	
		}	
		return -1;
	}
}

 

💡 깨달음

이 코드의 문제는 무엇일까!?

• 메모리 초과 발생
  • visited[r][c] >= visited[lo.row][lo.col]+1 코드를 보면
  • 값이 같을 때에도 조건이 만족되기 때문에 queue에 너무 많은 객체를 담게 된다
  • 사실 최단 경로💥 이기 때문에 값이 같을 때에는 굳이 해줄 필요가 없음!
• 벽 부수기로 인한 최단 경로 문제
  • 저 코드에서는 x, y 위치가 있을 때 이 위치에 도달하기 까지 벽을 부수고 온 경우와 부수지 않고 온 경우를 구별하지 못한다
  • 예를 들어 보쟈

 

가장 많은 반례로 등장한 입력이 있다. 우선 이 입력의 정답은 29이다. 

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

(7,1)에 접근하는 경우를 생각해보면

• (6,1)에서 접근할 수 있는데
  • 이때는 벽을 부수고 접근했기 때문에
  • 최단 거리 : 9
  • isBreak : 1
  • 이 되어 visited에는 9가 저장된다.
• (7, 0)
  • 여기서는 벽을 부수지 않고 직진해서 왔을 때
  • 최단 거리 : 9
  • isBreak : 0
  • 이 되어 이미 저장된 최단 거리와 같기 때문에 더이상 탐색을 진행하지 않지만 벽을 부쉈는지 여부가 다름
  • 정답 29는 (7,0)을 통해 (7,1)로 가는 루트
• 여기서 알 수 있는 점은 7,1의 위치에 대해 벽을 부수고 왔을 경우와 안 부수고 왔을 경우에 대해서
• 최단 경로를 각각 저장해주고 비교해줘야 한다는 것이다.
• (왜냐면 isBreak가 false인 상태로 7,0 -> 7,1을 지나 7,5의 벽을 부숴 도착해야하기 때문)

 

여기서 착안하여 visited 배열을 3차원으로 선언했다.

• int[][][] visited = new int[N][M][2] 로 하여 각 위치에 대해
• 0번 인덱스는 벽 부순 최단경로,
• 1번 인덱스는 벽 안부순 최단경로를 저장!

 

💡 최종 코드

최종 코드는 다음과 같다.

public class Main {
	
	private static int N, M;
	private static int[][] map;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split(" ");
		N = Integer.parseInt(line[0]);
		M = Integer.parseInt(line[1]);
		
		map = new int[N][M];
		
		for(int i=0; i<N; i++) {
			line = br.readLine().split("");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(line[j]);
			}
		}
		
		System.out.println(bfs(0, 0, N-1, M-1));
		
	}
	
	private static int bfs(int str_row, int str_col, int end_row, int end_col) {
		Queue<Location> queue = new ArrayDeque<Location>();
		queue.add(new Location(str_row, str_col, 0));
		
		// 0번째 안뿌숨, 1번째 뿌숨
		int[][][] visited = new int[N][M][2];
		visited[str_row][str_col][0] = 1;
		visited[str_row][str_col][1] = 1;
		
		int[] dr = {-1, 0, 1, 0};
		int[] dc = {0, 1, 0, -1};
		
		while(!queue.isEmpty()) {
			Location lo = queue.remove();

            if(lo.row == end_row && lo.col == end_col) {
				if(visited[end_row][end_col][0] == 0) return visited[end_row][end_col][1];
                if(visited[end_row][end_col][1] == 0) return visited[end_row][end_col][0];
				return Math.min(visited[end_row][end_col][0], visited[end_row][end_col][1]);
			}
			
			for(int d=0; d<4; d++) {
				int r = lo.row + dr[d];
				int c = lo.col + dc[d];
				
				if(r < 0 || r >=N || c < 0 || c >= M) continue;
				
				// 방문하지 않았거나 더 짧은 경로 인 경우
				if(visited[r][c][lo.isBreak] == 0 || visited[r][c][lo.isBreak] > visited[lo.row][lo.col][lo.isBreak]+1) {
					// 이동할 수 있을 경우
					if(map[r][c] == 0) {
						visited[r][c][lo.isBreak] = visited[lo.row][lo.col][lo.isBreak] +1;
						queue.add(new Location(r, c, lo.isBreak));
						continue;
					}
					
					// 벽일 경우 -> 아직 벽 뿌수기 안했다면
					if(lo.isBreak == 0) {
						visited[r][c][1] = visited[lo.row][lo.col][0] +1;
						queue.add(new Location(r, c, 1));
					}
				}
				
			}
			
		}
		return -1;
	}
}

class Location {
	int row;
	int col;
	int isBreak; // 0 or 1
	
	public Location(int r, int c, int isBreak) {
		this.row = r;
		this.col = c;
		this.isBreak = isBreak;
	}
}

• 이동가능한 상하좌우에 대해
• 벽을 부수고 도착한 경우, 안부수고 도착한 경우 각각
• 방문을 안했거나 더 작은 최단 경로 값을 가진 다면
• 두 가지 경우
  • 이동할 곳이 벽이 아니면
    • 최단 경로 값 갱신 후 탐색
  • 이동할 곳이 벽이면
    • 아직 벽을 안부쉈을 경우만
      • 벽을 부수고, 최단경로 갱신 후 탐색
• 도착지에 도달할 경우
  • 벽을 부쉈을 때만 도착했다면 벽을 부쉈을 경우의 최단 경로를
  • 벽은 안 부쉈을 때만 도착했다면 벽을 안 부쉈을 경우의 최단 경로를
  • 두 경우 모두 도착했다면 둘 중 최소값을 반환

 

 

결론

문제에서 주어진 입력 예제만으로는 알 수 없는 다양한 반례가 존재했다. 이를 찾아내는데 한세월....

조건도 복잡해서 잘 생각해내야 했고, 3차원 배열을 생각해내는게 중요했던 것 같다!!

고민할게 많았던 문제...🤔

 

 

반례 참고!!

https://www.acmicpc.net/board/view/66299

글 읽기 - 반례 모음집