[전체 코드]

// 알고스팟
package graphSearh;
import java.io.*;
import java.util.*;

public class BJ1261 {
    static int n, m;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		
		board = new int[n][m];
        visited = new boolean[n][m];
		
		for(int i = 0; i < n; i++) {
			String[] line = br.readLine().split("");
			for(int j = 0; j < m; j++) {
				int num = Integer.parseInt(line[j]);
				board[i][j] = num;
			}
		}
        
        solve();
    }

    public static void solve() {
        Deque<int[]> deque = new LinkedList<>(); 
        deque.add(new int[] {0, 0, 0});
        visited[0][0] = true;

        while (!deque.isEmpty()) {
            int[] cur = deque.poll(); // 맨 앞부터 poll
            // 도착했다면
            if (cur[0] == n - 1 && cur[1] == m - 1) {
                System.out.println(cur[2]);
                System.exit(0);
            }

            // 이동
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < m && !visited[nx][ny]) {
                    // 0이면 '앞'에 삽입
                    if (board[nx][ny] == 0) {
                        visited[nx][ny] = true;
                        deque.addFirst(new int[] {nx, ny, cur[2]});
                    } 
                    // 1이면 '뒤'에 삽입
                    else if (board[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        deque.add(new int[] {nx, ny, cur[2] + 1});
                    }
                }
            }
        }
    }
} 

[문제 풀이 설명]

이 문제는 보기에는 쉬워 보인다. 하지만, BFS, 백트래킹 등 푸는 방법이 확고하게 생각나지 않는 문제다.

일단, 이 문제는 최단 거리를 구하는 문제는 아니다. 하지만 왜 BFS를 썼냐?
Queue가 아닌 Deque의 성질을 사용하여서 BFS를 구현하였기 때문이다

일단 Deque가 뭔지 간단히 짚고 가자면,

Deque란 🔎

Queue는 한 방향으로 삽입/삭제한다. 하지만 Deque는 양방향(앞, 뒤) 으로 삽입/삭제를 할 수 있다.
(그리고 poll을 할 때에는 자동으로 앞에서부터 poll이 된다.)

위 문제는 벽을 최소 몇 번 부셨냐가 핵심인데, 그냥 BFS로 풀면 벽을 부수고 오던 말던, (n, m)까지의 최단 거리를 구해버린다. 하지만, 내가 이동할 때의 우선 순위를 두고 이동하는 것이다!

즉, 벽을 부수고 오지 않는 게 우선 순위가 더 높으므로, 0일 때의 경로를 deque에 앞으로 삽입하고, 1일 때의 경로를 deque에 뒤로 삽입하여 0인 곳으로 먼저 이동하는 것이다. 이때 벽을 부순 횟수는 deque에 함께 저장해주었다.

그럼 결과적으로 좀 돌아가더라도 0인 곳으로만 가게 되며, 비록 벽으로 막혀있다고 한들, BFS의 특징상 최종적으로 벽을 최소로 부수고 (n, m)에 도달하게 된다.

[어려웠던 점]

일단,

000
001
011

이렇게 정수형 행렬을 입력 받는 게 어려웠다,,
BufferedReader 등 입력 개념에 대해 공부가 더 필요하다.

그리고 분명 최단 거리를 구하는 게 아니기에 BFS를 사용하는 것은 아닌데, 백트래킹으로 풀기에는 너무 많은 시간 복잡도가 쓰일 것 같아서 혼란스러웠다. (= Deque를 생각해내지 못하였음.)

[느낀점]

시간 복잡도를 줄이기 위해 다양한 자료구조를 적절히 사용하자!