[BOJ] 2206 - 벽 부수고 이동하기

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

난이도: 골드 4

사용언어: JAVA

 

풀이

기본적으로는 BFS를 이용하여 해결하는 문제이며, 거기에 한 번 벽을 뚫을 수 있는 옵션을 추가한 형태입니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/63

[BOJ] 2178 - 미로 탐색

 

벽을 뚫는 것 자체는 쉽게 구현할 수 있습니다. 다른 BFS 문제들을 해결할 때 좌표에 대한 정보를 class로 선언하여 사용했는데, 이 클래스에 벽 뚫기 찬스를 사용했는지 안 했는지에 대한 정보만 추가해주면 됩니다.

 

그 외에 코드를 짜는 데 있어서 고려해야 할 사항들이 있습니다.

 

1. 원래는 한 번이라도 지나온 칸은 검사를 하지 않도록 어떤 값으로 마킹을 해주지만, 이 문제에서는 벽을 뚫고 온 경로를 벽을 안 뚫고 조금 더 돌아온 경로가 검사를 할 수 있어야 합니다. 이것을 고려해주지 않으면 출구가 1로 둘러싸여 있는 경우 등에서 틀리게 됩니다.

 

2. 벽을 뚫고 온 경우, 벽을 다시 세워줘야 합니다. 

 

3. N=1, M=1이고 입력이 0 하나만 있는 경우 등 예외 케이스를 생각해주어야 합니다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static class position {
        int x; // 행에 대한 좌표
        int y; // 열에 대한 좌표
        int c; // 뚫기 찬스를 썼는지 안썼는지 표시
    }
 
    static Queue<position> q = new LinkedList<>();
    static int cnt = 1;
    static int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 이동할 수 있는 4가지 방향
    static int N, M;
 
    public static void bfs(position p, char arr[][]) {
        int i;
        for (i = 0; i < 4; i++) {
            if (arr[p.x + d[i][0]][p.y + d[i][1]] == '0' || (arr[p.x + d[i][0]][p.y + d[i][1]] == '1' && p.c == 0) || (arr[p.x + d[i][0]][p.y + d[i][1]] == '3' && p.c == 0)) {
                position p1 = new position(); // 갈 곳이 빈칸이거나, 벽이지만 아직 뚫을 찬스가 남아있거나, 벽을 뚫고 온 경로가 지나간 위치인 경우
                p1.x = p.x + d[i][0];
                p1.y = p.y + d[i][1];
                if (p1.x == N && p1.y == M) { // 목적지에 도착
                    System.out.println(cnt + 1);
                    System.exit(0);
                }
                if (p.c == 0) { // 뚫기 찬스를 아직 안쓴 경우
                    p1.c = arr[p.x + d[i][0]][p.y + d[i][1]] == '1' ? 1 : 0; // 여기서 썼다면 1로 바꿔주고, 여기서도 안썼다면 0
                } else { // 뚫기 찬스를 이 전에 이미 쓰고 온 경우
                    p1.c = 1; // 그대로 1
                }
                arr[p1.x][p1.y] = p1.c == 0 ? '2' : '3'; // 뚫기 찬스를 쓴 경로라면 3, 아직 안쓰고 가는 경로라면 2
                if (p.c == 0 && arr[p1.x][p1.y] == '3') // 뚫기 찬스로 벽을 뚫은 경우
                    arr[p1.x][p1.y] = '1'; // 다시 벽을 세워줌
                q.add(p1); // 큐에 삽입
            }
        }
    }
 
    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());
 
        int i, j, k;
        String s;
        position p = new position();
        char[][] arr = new char[N + 2][M + 2];
        for (i = 1; i <= N; i++) {
            s = br.readLine();
            for (j = 1; j <= M; j++) {
                arr[i][j] = s.charAt(j - 1);
            }
       } // 편의상 (1,1)부터 출발할 수 있도록 1~N과 1~M으로 범위를 설정
 
        if (N == 1 && M == 1 && arr[1][1] == '0') { // 예외케이스 처리
            System.out.println("1");
            System.exit(0);
        }
 
        p.x = 1; // (1,1)에서 출발
        p.y = 1;
        p.c = 0; // 뚫기 찬스는 아직 쓰지 않았으니 0
        arr[1][1] = '2';
        q.add(p);
        while (true) {
            if (q.size() == 0) { // 더이상 움직일 곳이 없으면 -1 출력하고 프로그램 종료
                System.out.println(-1);
                System.exit(0);
            }
            k = q.size();
            for (i = 0; i < k; i++) { // 큐에 있는 모든 요소를 빼면서
                p = q.remove();
               bfs(p, arr); // bfs 수행
            }
            cnt++; // 몇 번째인지 카운트
        }
    }
}