[Java Algorithm] 벽 부수고 이동하기 BOJ #2206

문제

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

2206번: 벽 부수고 이동하기

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	static int[] dx = {0, 0 ,-1, 1};
	static int[] dy = {-1, 1, 0, 0};
	static Deque<int[]> que;
	static char[][] map;
	static int n;
	static int m;
	static int[][][] visited; // 자리마다 벽을 부수고 왔는지, 안부수고 왔는지를 저장
	
	public static int bfs() {
		while(!que.isEmpty()) {
			int[] now = que.removeFirst();
			int x = now[0];
			int y = now[1];
			int z = now[2];
			
			if(x == n-1 && y == m-1) return visited[x][y][z];
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
				
				if(visited[nx][ny][z] == 0) {
					// 벽이 있는데, 이전까지는 벽을 부수지 않았던 경우 (== 부술 수 있는 경우)
					if(map[nx][ny] == '1' && z == 1) {
						visited[nx][ny][0] = visited[x][y][1] + 1;
						que.add(new int[]{nx, ny, 0});
					}
					// 벽이 아닌 경우
					else if(map[nx][ny] == '0') {
						visited[nx][ny][z] = visited[x][y][z] + 1;
						que.add(new int[]{nx, ny, z});
					}
				}
			}
		}
		
		return -1;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new char[n][m];
		
		for(int i = 0; i < n; i++) {
			String tmp = in.readLine();
			for(int j = 0; j < m; j++) {
				map[i][j] = tmp.charAt(j);
			}
		}
		
		que = new ArrayDeque<>();
		que.add(new int[]{0, 0, 1}); // {x좌표, y좌표, 벽을 부쉈는지 아닌지} (부순 경우 0, 부수지 않은 경우 1)
		visited = new int[n][m][2];
		visited[0][0][1] = 1; // [][][0]은 부순적 있는 경우, [][][1]은 부순적 없는 경우에 대한 누적 시간을 저장
		
		System.out.println(bfs());
	}

}

👉 BFS 문제

[ 변수 설명 ]

• dx, dy
  상하좌우 탐색을 위한 좌표 배열
• que
  bfs 탐색 중 새롭게 탐색할 좌표값과 벽을 부쉈는지 여부를 저장할 덱
  (x좌표, y좌표, 벽을 부순적 있는지 여부(부순적 있으면 0, 부수지 않았으면 1))
• visited
  입력되는 맵과 같은 크기의 배열인데, 자리마다 벽을 부순적 있는지 없는지에 대한 경우를
  나눠서 방문 체크를 하기 위해 3차원 배열로 확장시켜서 만들어주었다.
  ([][][0] 자리가 0이 아니면 벽을 부순 적 있고, [][][1] 자리가 0이 아니면 부순적 없다는 뜻)

 

[ 풀이 설명 ]

• bfs 탐색 전, 첫 번째 자리에서는 당연히 벽을 부수지 않으므로 que에 {0, 0, 1}을 추가했고,
  visited에도 벽을 부수지 않는 자리인 [0][0][1]에 1을 저장해주었다.
• bfs 메서드에서는 que가 비어있게 되기 전까지 while문을 반복하도록 했는데,
  만약 x, y가 도착 지점의 좌표값과 같을 시 return하도록 했다. (가장 빠른 도착)
• 같지 않을 경우에는 for문을 이용하여 상하좌우를 탐색했다.
  visited 배열의 해당하는 자리에 1이 저장되어있다면 이미 방문한 자리라는 뜻이므로
  따로 조건을 정해주지 않았고, 0이 저장된 경우에만 새로운 탐색을 해주었다.
• 만약 map[nx][ny]에 1(벽)이 저장되어있는데, z가 1이라면 벽을 부술 수 있다는 뜻이므로,
  벽을 부수고 다음 자리로 나아갈 수 있다는 의미이다. 따라서 우리는 벽을 부술 것이며,
  한 번 부쉈다는 것을 표시하기 위해 visited[nx][ny][0]에 visited[x][y][1] + 1을 저장했다.
• 만약 map[nx][ny]에 0이 저장되어있다면 이전에 벽을 부쉈든 안부쉈든 (z가 0이든 1이든)
  무조건 다음 자리로 이동할 수 있다는 의미이다. 따라서 우리는 다음으로 이동할 것이며,
  visited[nx][ny][z]에 visited[x][y][z] + 1을 저장해주었다.
• while 반복이 끝날 때까지 bfs 함수가 리턴되지 않았다면 도착 불가로 판단, -1을 리턴했다.

 

💡 피드백

• visited 배열과 que 요소에 대한 판단이 복잡해서 헷갈리기도 했지만 어렵지 않은 문제였다.