모각코PS / 백준 2178 미로 탐색

모각코 PS스터디

그래프 탐색 두 번째 문제인 '미로 탐색'입니다.

문제의 제약조건을 보면서 어떤 알고리즘으로 접근하면 좋을지 힌트를 얻을 수 있기도 하죠?
표본 수가 적고, 시간 제한이나 메모리가 상대적으로 넉넉하고, 좌표나 맵 같은 것이 주어지면 그래프가 떠오르는 것 같습니다.
그리고 각 탐색로의 길이를 비교하거나, 특히 가장 빠른 탐색 경로를 찾아야 하는 경우에는 BFS를 선택하는 편이 '대개' 유리하겠죠. 모든 경로를 다 들어가보고 길이를 기록해뒀다가 제일 짧은 길이를 리턴하는 것보다, 모든 경로를 동시에 진행하다가 한 경로가 끝에 다다르면 나머지를 더이상 탐색하지 않고 리턴하는게, 탐색 횟수가 훨씬 적을 거니까요.

이번 문제가 그런 스타일의 문제였습니다.

문제와 풀이

---

문제 링크 : 백준 2178 - 미로 탐색

👇펼쳐서 코드와 해설 읽기

BFS를 Queue로 구현했어요. BFS 구현 자체는 특별할게 없네요.
현재 탐색 step을 기록하기 위해서 따로 레벨을 세어주진 않았고요, 대신 탐색한 노드(Room class) 자체에 step을 기록하는 필드를 하나 선언해뒀어요. 방문할 때에 step을 기록해두는 거죠.
그리고 BFS 탐색이 목표지점에 다다르면 탐색을 마칩니다. 그리고 콘솔에 출력하고 끝이에요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Nick {

    static int n;
    static int m;
    static int[][] maze;

    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());
        maze = new int[n][m];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            if (line == null || line.isEmpty()) {
                break;
            }

            char[] carr = line.toCharArray();
            for (int j = 0; j < m; j++) {
                maze[i][j] = carr[j] == '1' ? 1 : 0;
            }
        }
        br.close();

        find(0, 0);
    }

    private static void find(int x, int y) {
        Queue<Room> bfsQueue = new LinkedList<>();
        visitNewRoom(bfsQueue, 1, x, y);

        Room room = null;
        while (!bfsQueue.isEmpty()) {
            room = bfsQueue.poll();
            int nowX = room.getX();
            int nowY = room.getY();

            // 중단 조건 : 목적지에 도착했다면, 탐색 종료(현재 room정보를 가진 채로).
            if (nowX == n - 1 && nowY == m - 1) break;

            if (0 < nowX
                    && maze[nowX - 1][nowY] == 1) {
                visitNewRoom(bfsQueue, room.getNextStep(), nowX - 1, nowY);
            }
            if (nowX < n - 1
                    && maze[nowX + 1][nowY] == 1) {
                visitNewRoom(bfsQueue, room.getNextStep(), nowX + 1, nowY);
            }
            if (0 < nowY
                    && maze[nowX][nowY - 1] == 1) {
                visitNewRoom(bfsQueue, room.getNextStep(), nowX, nowY - 1);
            }
            if (nowY < m - 1
                    && maze[nowX][nowY + 1] == 1) {
                visitNewRoom(bfsQueue, room.getNextStep(), nowX, nowY + 1);
            }
        }

        if (room != null) System.out.println(room.getStep());
    }

    private static void visitNewRoom(Queue<Room> bfsQueue, int room, int nowX, int nowY) {
        bfsQueue.add(new Room(room, nowX, nowY));
        maze[nowX][nowY]++;
    }

}
class Room {
    private final int posStep;
    private final int posX;
    private final int posY;
    public Room(int step, int x, int y) {
        posStep = step;
        posX = x;
        posY = y;
    }
    public int getX() {
        return posX;
    }
    public int getY() {
        return posY;
    }
    public int getStep() { return posStep; }
    public int getNextStep() { return posStep + 1; }
}

마무리

---

이번 문제도 이전 문제와 같이 두 분(o_b:us님, 소토님)의 코드를 참고하며 셀프 리뷰했습니다. :)

탐색할 경로를 좌표 배열로 지정하는 게 기본적인 코딩 스타일이었던 것을, 두 분 코드를 보고 나서야 떠올렸어요. if문으로 도배할 필요가 없었는데 말이죠...ㅎㅎ. 적용하면 코드를 많이 줄일 수 있겠네요.

그리고 원래 결과값을 출력하고 return 하는 코드가 while문 안에 있었어요. 근데 생각해보니까 이게 좋은 방식이 아닌 것 같더라구요.
출력은 종료되기 직전에 실행되는 거니까, 코드 상에서도 끝 단에 있으면 코드 파악하기가 좋겠단 생각이 들었어요. 저는 분명 제가 짠 코드인데도 며칠만에 보니까 "출력하는 코드는 어디있는거야?"라는 생각이 들더라구요. 그래서 이건 바로 수정했습니다.

이것도 그래프 탐색에 익숙하기만 하다면 쉽게 풀 수 있는 문제였던 것 같아요. 그러면 PS 리뷰 마치겠습니다!