[BaekJoon] 2206 벽 부수고 이동하기 (Java)

1.  문제 링크

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

2.  문제

요약

• NxM의 행렬로 표현되는 맵이 있고, 맵에서 0은 이동할 수 있는 곳을, 1은 이동할 수 없는 벽이 있는 곳을 나타냅니다.
• 이때 최단 경로로 이동하려고 하는데, 시작하는 칸과 끝나는 칸도 포함해서 셉니다.
• 만약 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개까지 부수고 이동하여도 됩니다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸입니다.
• 맵이 주어졌을 때, 최단 경로를 구하는 문제입니다.
• 입력: 입력은 1보다 크거나 같고 1000보다 작거나 같은 N과 M이 주어지고 두 번째 줄부터 N개의 줄에는 M개의 숫자로 맵이 주어집니다.
  • (1, 1)과 (N, M)은 항상 0이라고 가정합니다.
• 출력: 첫 번째 줄에 최단 거리를 출력합니다. 불가능할 때는 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[][] map;
	static int[][] count;
	static boolean[][][] visited;
	static int min;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		min = Integer.MAX_VALUE;
		map = new int[N][M];
		visited = new boolean[N][M][2];
		for(int i = 0; i < N; i++) {
			String input = scanner.nextLine();
			for(int j = 0; j < M; j++) {
				map[i][j] = input.charAt(j) - '0';
			}
		}
	}
	
	static void solution() {
		if(N == 1 && M == 1) {
			System.out.println(1);
			return;
		}
		bfs();
		min = min == Integer.MAX_VALUE ? -1 : min;
		System.out.println(min);
	}
	
	static void bfs() {
		Queue<Point> queue = new LinkedList<Point>();
		queue.offer(new Point(0, 0, 1, false));
		while(!queue.isEmpty()) {
			Point cur_point = queue.poll();
			if(cur_point.x == N - 1 && cur_point.y == M - 1) {
				min = cur_point.count;
				return;
			}
			for(int i = 0; i < 4; i++) {
				int cx = cur_point.x + dx[i];
				int cy = cur_point.y + dy[i];
				if(cx >= 0 && cx < N && cy >= 0 && cy < M) {
					if(map[cx][cy] == 0) {
						if(!cur_point.destroy && !visited[cx][cy][0]) { // 이전에 벽을 부신 적이 없는 경우
							queue.offer(new Point(cx, cy, cur_point.count + 1, false));
							visited[cx][cy][0] = true;
						} else if(cur_point.destroy && !visited[cx][cy][1]) { // 이전에 벽을 이미 부신 경우
							queue.offer(new Point(cx, cy, cur_point.count + 1, true));
							visited[cx][cy][1] = true;
						}
					} else if(map[cx][cy] == 1) {
						if(!cur_point.destroy) {
							queue.offer(new Point(cx, cy, cur_point.count + 1, true));
							visited[cx][cy][1] = true;
						}
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			return str;
		}
	}
	
	static class Point {
		int x, y, count;
		boolean destroy;
		public Point(int x, int y, int count, boolean destroy) {
			this.x = x;
			this.y = y;
			this.count = count;
			this.destroy = destroy;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• N이 1, M이 1이라면 시작하는 칸과 끝나는 칸이 같기 때문에 1을 출력합니다.
• 그렇지 않다면 BFS를 이용하여 최단 경로를 찾습니다.
• BFS 탐색을 위해 Queue를 생성하고 visited 배열을 생성합니다.
• visited 배열은 3차원 배열로 이루어져있고 visited 배열은 아래와 같은 의미를 지닙니다.
  • visited[x][y][0] : 벽을 한 번도 부수지 않은 상태에서 (x, y)를 방문하였는지
  • visited[x][y][1] : 벽을 한 번 부수고 (x, y)를 방문하였는지
• Queue에 시작점을 넣고 Queue가 비워지기 전까지 Queue에서 방문할 위치를 하나씩 꺼내서 각 위치들을 탐색합니다.
  • 만약 현재 위치가 (N, M)이라면, 즉 끝나는 칸이라면 최단 경로의 길이를 나타내는 변수 min을 갱신하고 이를 출력합니다.
    • 만약 min이 초기값과 같다면 최단 경로가 존재하지 않는다는 뜻이므로 -1을, 그렇지 않다면 min값을 출력합니다.
  • 그렇지 않다면 상하좌우 위치를 각각 확인하여 해당 위치를 탐색할 필요가 있는지 확인합니다.
    1. 해당 위치가 맵 내에 존재하고 해당 위치의 값이 0이라면, 즉 벽이 아니라면
       1. 이전에 벽을 부신 적이 없을 경우
          • 상하좌우로 이동할 위치를 (cx, cy)라고 한다면 visited[cx][cy][0]의 값을 true로 변경하여 방문처리를 진행합니다.
          • 그리고 이후에 이 위치를 탐색하기 위해 Queue에 (cx, cy) 위치 및 (현재 탐색하는 위치의 이동 횟수 + 1), false 값을 넣습니다.
          • Queue에 위와 같이 4개의 값을 넣는데 이는 Queue에 Point 클래스를 넣기 때문에 4개의 값을 넣습니다.
            • Point 클래스는 (x 좌표, y 좌표, 현재 위치까지 이동하는 데에 걸린 횟수, 이전까지 벽이 부셔졌는지 여부)를 나타냅니다.
       2. 이전에 벽을 이미 부신 경우
          • 상하좌우로 이동할 위치를 (cx, cy)라고 한다면 visited[cx][cy][1]의 값을 true로 변경하여 방문처리를 진행합니다.
          • 그리고 이후에 이 위치를 탐색하기 위해 Queue에 (cx, cy) 위치 및 (현재 탐색하는 위치의 이동 횟수 + 1), true 값을 넣습니다.
          • 이전에 벽을 이미 부신 경우이기 때문에 Point 클래스에서 이전까지 벽이 부셔졌는지 여부를 true로 하여 Queue에 넣습니다.
    2. 해당 위치가 맵 내에 존재하고 해당 위치의 값이 1이라면, 즉 벽이라면
       • 이전에 벽을 부신 적이 있는지 확인하고 그렇지 않다면 해당 위치의 벽을 부십니다.
         • 상하좌우로 이동할 위치를 (cx, cy)라고 한다면 visited[cx][cy][1]의 값을 true로 변경하여 방문처리를 진행합니다.
         • 그리고 Queue에 (cx, cy) 위치 및 (현재 탐색하는 위치의 이동 횟수 + 1), true 값을 Queue에 넣습니다.