[java] 백준 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 Boj_2178
{
    static int[][] arr; // 미로
    static boolean[][] visited; // 방문 체크
    static int n;
    static int m;

    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());

        visited = new boolean[n][m];
        arr = new int[n][m];
        for(int i = 0; i < n; ++i)
        {
            char[] charArray = br.readLine().toCharArray(); // 문자열을 문자 배열로 변환
            for(int j = 0; j < m; ++j) arr[i][j] = Character.getNumericValue(charArray[j]); // 각 문자를 숫자로 변환하여 배열에 저장
        }

        BFS(0, 0); // (0, 0)부터 최단경로 탐색 시작
        System.out.println(arr[n - 1][m - 1]);
    }

    static void BFS(int startX, int startY)
    {
        int[] dy = { -1, 1, 0, 0 }; // y축(상, 하)
        int[] dx = { 0, 0, -1, 1 }; // x축(좌, 우)
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] {startY, startX}); // 큐에 시작 좌표를 넣음
        visited[startY][startX] = true; // 시작 좌표는 방문 처리

        while(!que.isEmpty()) // 큐가 비어있지 않았다면
        {
            int now[] = que.poll(); // 큐에서 좌표를 꺼냄
            int nowY = now[0]; // y좌표
            int nowX = now[1]; // x좌표

            for(int i = 0; i < 4; ++i) // 상하좌우로 다음 탐색할 좌표를 입력
            {
                int nextY = nowY + dy[i]; // 다음 탐색할 y좌표
                int nextX = nowX + dx[i]; // 다음 탐색할 x좌표

                if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= m) continue; // 다음 탐색할 좌표 유효성 검사
                else if (visited[nextY][nextX] || arr[nextY][nextX] == 0) continue; // 다음 탐색할 좌표가 이미 방문했거나, 벽이라면 pass
                else
                {
                    visited[nextY][nextX] = true; // 방문 표시
                    arr[nextY][nextX] = arr[nowY][nowX] + 1; // 이동한 칸 수 업데이트
                    que.offer(new int[] {nextY, nextX}); // 큐에 삽입
                }
            }
        }
    }
}

 

설명

• N과 M의 최대 크기가 100으로 매우 작기 때문에 시간 제한은 별도로 생각하지 않아도된다.
• 문제의 요구사항은 지나야 하는 칸 수의 최솟값을 찾는 것이기 때문에 DFS가 아니라 BFS를 사용해야 한다.
• 따라서 BFS를 사용해 최초로 도달했을 때 깊이를 출력하면 문제를 해결할 수 있다.

 

이 테스트 케이스를 예로들면, 2차원 배열에 데이터를 저장하고 시작 지점에서 BFS를 진행한다.

상, 하, 좌, 우 네 방향을 보며 인접한 칸의 숫자가 0이 아니면서, 아직 방문하지 않았다면 큐에 삽입한다.

이 때, 해당 배열을 방문 처리하면서, 인접 배열의 값을 BFS의 깊이로 업데이트한다.