[JAVA] BOJ 백준 2206번 - 벽 부수고 이동하기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2206번: 벽 부수고 이동하기

---

2. 내가 푼 방법

다양한 난이도의 BFS 문제를 풀다 보면, 어떻게 풀어야 할지 감이 잡히는 문제이다.

일반 BFS 풀이 과정에서 경로를 지나친적이 있는지 확인하는 check 변수를 잘 설정해주면 되는 게 포인트이다.

 

이번 문제에서는 벽을 한번 부숴 지나쳤는지, 벽을 부시지 않고 지나쳤는지에 대한 것을 삼차원 배열 check[][][]로 선언해 줬다.

check[(부순적있는지에 대한 0, 1)][(x 값)][(y 값)] 을 설정하여 이동을 확인했고, 그 후 이동하려는 공간이 벽일 때 벽을 부수거나 더 이상 이동할 수 없는 경우를 판단해 주면 된다.

---

3. 자바 코드

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

class B2206 {
    static int sero;
    static int garo;
    static char[][] arr;
    static boolean[][][] check;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        sero = Integer.parseInt(st.nextToken());
        garo = Integer.parseInt(st.nextToken());

        arr = new char[sero][garo];
        for (int i = 0; i < sero; i++) {
            String line = br.readLine();
            for (int j = 0; j < garo; j++) {
                arr[i][j] = line.charAt(j);
            }
        }

        check = new boolean[2][sero][garo];
        bw.write(bfs()+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static int bfs () {
        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(0, 0, 1, 0));

        int count = -1;
        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            int x = tuple.x;
            int y = tuple.y;
            int depth = tuple.depth;
            int broken = tuple.broken;

            if (x == sero-1 && y == garo-1) {
                count = depth;
                break;
            }
            if (x < 0 || y < 0 || x == sero || y == garo) continue;
            if (check[broken][x][y]) continue;
            if (broken == 1 && arr[x][y] == '1') continue; // 벽일 경우 + 이미 부순 경우 -> 더이상 이동 X

            check[broken][x][y] = true;

            if (arr[x][y] == '1') { // 벽일 경우 무조건 깨부숨 (broken 1 설정)
                queue.add(new Tuple(x-1, y, depth+1, 1));
                queue.add(new Tuple(x+1, y, depth+1, 1));
                queue.add(new Tuple(x, y-1, depth+1, 1));
                queue.add(new Tuple(x, y+1, depth+1, 1));
            }
            else { // 벽이 아닐 경우 그대로 (기존 broken 설정)
                queue.add(new Tuple(x - 1, y, depth + 1, broken));
                queue.add(new Tuple(x + 1, y, depth + 1, broken));
                queue.add(new Tuple(x, y - 1, depth + 1, broken));
                queue.add(new Tuple(x, y + 1, depth + 1, broken));
            }
        }
        return count;
    }

    public static class Tuple {
        int x;
        int y;
        int depth;
        int broken;

        public Tuple (int x, int y, int depth, int broken) {
            this.x = x;
            this.y = y;
            this.depth = depth;
            this.broken = broken;
        }
    }
}

---

4. 결과 및 회고

처음 이런 문제를 봤을 때 쉬운 것 같지만, 어떻게 접근해야 하는지 감이 안 잡혔다. 그래서 다른 사람의 코드를 보고 풀었는데 이제는 학습이 돼서 내재화된 것 같다. 다행이다.