[백준 / Java] 2206번 : 벽 부수고 이동하기

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력 1 복사

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1 복사

15

예제 입력 2 복사

4 4
0111
1111
1111
1110

예제 출력 2 복사

-1

---

문제 풀이

 해당 문제는 기존의 DFS 문제와 유사하다. 하지만 벽을 부술 수 있다는 예외 케이스가 존재한다. 그렇기에 처음 구현했을 때 아래와 같이 Positon class를 만들어 벽을 부술 기회가 남아있다면 벽도 지날 수 있도록 지정해두었다.

 코드는 아래와 같다.

import java.util.*;
import java.io.*;
public class Main {

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static int[][] board;
	public static boolean[][] visited;
	
	public static Queue<Position> qu = new LinkedList<>();
	
	public static int[] dx = {0,1,0,-1};
	public static int[] dy = {-1,0,1,0};
	
	public static class Position {
		int x;
		int y;
		boolean chance = true;
		int distance;
		
		public Position() {
			// TODO Auto-generated constructor stub
		}

		public Position(int x, int y, boolean chance,int distance) {
			super();
			this.x = x;
			this.y = y;
			this.chance = chance;
			this.distance = distance;
		}
	}
	
	public static void main(String[] args) throws IOException{
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int answer = -1;
		
		board = new int[R][C];
		visited = new boolean[R][C];
		
		
		
		for(int i = 0; i < R; i++) 
			board[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
		

		qu.add(new Position(0,0,true,1));
		
		while(!qu.isEmpty()) {
			Position cur = qu.poll();
			
			if(cur.x == C - 1 && cur.y == R - 1) {
				answer = cur.distance;
				break;
			}
			
			if(visited[cur.y][cur.x])continue;
			visited[cur.y][cur.x] = true;
			
			for(int i = 0; i < 4; i++) {
				int mx = cur.x + dx[i];
				int my = cur.y + dy[i];
				
				if(mx < 0 || mx >= C || my < 0 || my >= R)continue;
				
				if(cur.chance) {
					if(board[my][mx] == 0) {
						qu.add(new Position(mx,my,true,cur.distance+1));
					}else {
						qu.add(new Position(mx,my,false,cur.distance+1));
					}
				}else {
					if(board[my][mx] == 0) {
						qu.add(new Position(mx,my,false,cur.distance+1));
					}
				}
			}
		}
		if(R == 1 && C == 1) 
			System.out.println(0);
		else
		System.out.println(answer);
		
	}
	
}

 

하지만 테스트케이스 15%쯤 오답이 나왔다.

 

 

오답이 나오는 케이스는 아래와 같은 케이스였다.

 

7 5
00000
11110
00000
01111
00000
11111
00000

 위와 같은 케이스에서는 (1,0)을 벽으로 부수고 아래로 진출 할 때 visited[1][0]에서 벽을 부수지 않고 돌아서 진출했을 때 진행을 하지 못하여 -1을 출력하였다.

 빨간 케이스(벽을 부순 경우)로 인해 파란 케이스(벽을 부수지 않은 경우)가 막혀 답이 나오지 않는 것이다.

 

그렇기에 벽을 부순 경우는 visited를 별도로 만들어서 구현해보았고, 문제를 해결할 수 있었다.

---

해결 코드

import java.util.*;
import java.io.*;
public class Main {

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static int[][] board;
	public static boolean[][] visited;
	public static boolean[][] visited2;
	
	public static Queue<Position> qu = new LinkedList<>();
	
	public static int[] dx = {0,1,0,-1};
	public static int[] dy = {-1,0,1,0};
	
	public static class Position {
		int x;
		int y;
		boolean chance = true;
		int distance;
		
		public Position() {
			// TODO Auto-generated constructor stub
		}

		public Position(int x, int y, boolean chance,int distance) {
			super();
			this.x = x;
			this.y = y;
			this.chance = chance;
			this.distance = distance;
		}

		@Override
		public String toString() {
			return "Position [x=" + x + ", y=" + y + ", chance=" + chance + ", distance=" + distance + "]";
		}
	}
	
	public static void main(String[] args) throws IOException{
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int answer = -1;
		
		board = new int[R][C];
		visited = new boolean[R][C];
		visited2 = new boolean[R][C];
		
		
		for(int i = 0; i < R; i++) 
			board[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
		

		qu.add(new Position(0,0,true,1));
		
		while(!qu.isEmpty()) {
			Position cur = qu.poll();
			if(cur.x == C - 1 && cur.y == R - 1) {
				answer = cur.distance;
				break;
			}
			
			if(cur.chance) {
				if(visited[cur.y][cur.x])continue;
				else {
					visited2[cur.y][cur.x] = true;
					visited[cur.y][cur.x] = true;
				}
				
			}else {
				if(visited2[cur.y][cur.x])continue;
				else 
					visited2[cur.y][cur.x] = true;
			}
			
			
			
			for(int i = 0; i < 4; i++) {
				int mx = cur.x + dx[i];
				int my = cur.y + dy[i];
				
				if(mx < 0 || mx >= C || my < 0 || my >= R)continue;
				
				if(cur.chance) {
					if(board[my][mx] == 0) {
						qu.add(new Position(mx,my,true,cur.distance+1));
					}else {
						qu.add(new Position(mx,my,false,cur.distance+1));
					}
				}else {
					if(board[my][mx] == 0) {
						qu.add(new Position(mx,my,false,cur.distance+1));
					}
				}
			}
		}
		System.out.println(answer);
		
	}
	
}