[2178] - 미로 탐색

문제

---

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

 

 

풀이

---

 

먼저 코드부터 보자.

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 Miro {
    static class Node {
        int x;
        int y;
        int cnt;
        public Node(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }

    static int[][] miro;
    static boolean[][] visited;
    static int N, M;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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());
        
        miro = new int[N][M];
        visited = new boolean[N][M];
        
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                miro[i][j] = line.charAt(j) - '0';
            }
        }
        
        int result = bfs(0, 0);
        System.out.println(result);
    }

    public static int bfs(int startX, int startY) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(startX, startY, 1));
        visited[startX][startY] = true;
        
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            
            if (current.x == N - 1 && current.y == M - 1) {
                return current.cnt;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M 
                    && !visited[nx][ny] && miro[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    queue.offer(new Node(nx, ny, current.cnt + 1));
                }
            }
        }
        
        return -1;
    }
}

 

 

문제를 읽어보면 바로 알겠지만 너비 우선 탐색을 사용해야 한다. BFS를 적용해본 지 오래라 기억이 희미해서 시간이 좀 걸렸다.

여하튼 본론으로 들어가자.

 

1. 2차원 배열을 지도라 생각하고 사람 한 명이 최단로를 걸으면서 발자국을 남겼다고 하자. 그 발자국이 '1'이다.
2. 지도 안에서는 상하좌우로 움직일 수 있으니 각각의 위치를 찾을 필요가 있다. 따라서 Node 클래스를 만들어 현재 위치를 갱신토록 하고, dx와 dy 배열을 생성해 오갈 수 있는 위치(너비)는 전부 찾아보도록 한다.

 

if (nx >= 0 && 
	nx < N && 
    ny >= 0 && 
    ny < M &&
    !visited[nx][ny] &&
    miro[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    queue.offer(new Node(nx, ny, current.cnt + 1));
                }

 

일반적인 bfs고 bfs에서 역시 중요한 게 조건문이다. 위 코드를 보면 이동하려는 칸이 상하좌우 범위 내에 있고, 방문하지 않았으면서 이동가능한 칸(1)인 경우에만 이동할 수 있도록 했다.