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

문제

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

풀이

• N×M의 맵
• 0: 이동할 수 있는 곳, 1: 이동할 수 없는 벽
• (1, 1) 에서 (N, M)의 위치까지 이동
• 벽을 부수고 이동하는 것이 더 짧다면, 벽을 "한 개"까지 부수고 이동 가능
• 맵이 주어졌을 때, 최단 경로 출력

BFS 알고리즘을 활용한 문제
벽 부숨 여부와 부수고 이동했을 때, 부수지 않고 이동했을 때의 방문 여부를 따로 저장하면 쉽게 해결할 수 있습니다.

입력

	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()); // 가로
		
        // 지도 및 방문여부 초기화
		map = new int[n][m];
		visited = new boolean[n][m][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';
			}
		}

• 방문 여부는 벽을 부쉈을 때와 부수지 않았을 때를 나눠 저장하기 위해 3차원 배열로 선언하였습니다.

현재 위치를 관리하기 위한 클래스

	static class Loc {
		int r, c, dist; // 좌표 (r, c), 이동한 거리
		boolean used; // 벽 부숨 여부
		
		public Loc (int r, int c, int dist, boolean used) {
			this.r = r;
			this.c = c;
			this.dist = dist;
			this.used = used;
		}
	}

• 현재 좌표 (r, c), 이동한 거리, 벽 부숨 여부를 클래스로 관리

탐색

	static final int[] dr = { -1, 1, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1 };
	
	private static int bfs() {
    	// BFS 탐색을 위해 큐 선언
		Queue<Loc> queue = new ArrayDeque<>();
		queue.add(new Loc(0, 0, 1, false));
		
        // 시작지점 방문 처리
		visited[0][0][0] = true;
		
		while (!queue.isEmpty()) {
			Loc cur = queue.poll();
			int r = cur.r;
			int c = cur.c;
			
            // 도착했다면 이동한 거리 리턴
			if (r == n-1 && c == m-1) return cur.dist;
			
            // 4방탐색
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
				
				// 다음 경로 탐색
				// 벽이 아닐 경우
				if (map[nr][nc] == 0) {
                	// 방문하지 않은 좌표로만 이동
                    // 벽을 부수지 않고 이동하고 있었다면
					if (!cur.used && !visited[nr][nc][0]) {
						queue.add(new Loc(nr, nc, cur.dist + 1, false));
						visited[nr][nc][0] = true;
					}
                    // 벽을 이미 부쉈다면
                    else if (cur.used && !visited[nr][nc][1]) {
						queue.add(new Loc(nr, nc, cur.dist + 1, true));
						visited[nr][nc][1] = true;
					}
				}
				// 벽일 경우
				else {
                	// 벽을 부수지 않았고, 방문하지 않은 좌표
					if (!cur.used && !visited[nr][nc][1]) {
						queue.add(new Loc(nr, nc, cur.dist + 1, true));
						visited[nr][nc][1] = true;
					}
				}
			}
		}
		
		return -1; // 도착지에 도달하지 못했다면 -1 리턴
	}

• visited[r][c][0]: 벽을 부수지 않고 이동했는지 여부
• visited[r][c][1]: 벽을 부수고 이동했는지 여부

출력

		System.out.println(bfs());

• 바로 출력해주면 됩니다.

여기서 중요한 점은 "벽 부숨 여부"와 "벽을 부수고 이동했을 때, 벽을 부수지 않고 이동했을 때"의 방문 여부를 저장하는 겁니다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static class Loc {
		int r, c, dist;
		boolean used;
		
		public Loc (int r, int c, int dist, boolean used) {
			this.r = r;
			this.c = c;
			this.dist = dist;
			this.used = used;
		}
	}
	
	static int n, m;
	static int[][] map;
	static boolean[][][] visited;
	
	static final int[] dr = { -1, 1, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1 };
	
	private static int bfs() {
		Queue<Loc> queue = new ArrayDeque<>();
		queue.add(new Loc(0, 0, 1, false));
		
		visited[0][0][0] = true;
		
		while (!queue.isEmpty()) {
			Loc cur = queue.poll();
			int r = cur.r;
			int c = cur.c;
			
			if (r == n-1 && c == m-1) return cur.dist;
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
				
				// 다음 경로 탐색
				// 벽이 아닐 경우
				if (map[nr][nc] == 0) {
					if (!cur.used && !visited[nr][nc][0]) {
						queue.add(new Loc(nr, nc, cur.dist + 1, false));
						visited[nr][nc][0] = true;
					} else if (cur.used && !visited[nr][nc][1]) {
						queue.add(new Loc(nr, nc, cur.dist + 1, true));
						visited[nr][nc][1] = true;
					}
				}
				// 벽일 경우
				else {
					if (!cur.used && !visited[nr][nc][1]) {
						queue.add(new Loc(nr, nc, cur.dist + 1, true));
						visited[nr][nc][1] = true;
					}
				}
			}
		}
		
		return -1;
	}
	
	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());
		
		map = new int[n][m];
		visited = new boolean[n][m][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';
			}
		}
		
		System.out.println(bfs());
	}

}