[2178] 미로탐색

🔗 문제 링크

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

❔ 문제 설명

		  1	  0	  1	  1	  1	  1
		  1	  0	  1	  0	  1	  0
		  1	  0       1	  0	  1	  1
		  1	  1	  1	  0	  1	  1

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

⚠️ 제한사항

• 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

• 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

---

💡 풀이 (언어 : Java & Python)

BFS로 DP처럼 시작점에서 해당 지점까지 도달하는 최단 거리를 원본 배열 해당 지점에 적어준다. 그 후에 다른 지점에서 연결되어서 방문하여 다시 탐색하지 않도록 boolean 이차원 배열로 방문처리로 체크한다. 마지막 지점의 결과값이 정답이다. BFS이므로 제일 먼저 정답을 만족하는 값이 최단거리이다. 이후 값들은 visited = true이므로 적용되지 않는다.

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    private int findMinDistance(int n, int m, int[][] maze) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        // 첫 시작점 큐에 넣고, 방문처리
        queue.add(new int[] {0, 0});
        visited[0][0] = true;
        // BFS
        while(!queue.isEmpty()) {
            int[] point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = point[0] + dirs[i][0], ny = point[1] + dirs[i][1];
                // 범위를 넘거나, 이미 방문했거나, 갈수 없는 길이면 스킵
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] || maze[nx][ny] == 0)
                    continue;
                // 시작점부터 이전 지점까지의 거리 + 1은 향할 지점의 최단거리, 해당 지점에 적고 방문처리 후 큐에 넣기
                maze[nx][ny] = maze[point[0]][point[1]] + 1;
                visited[nx][ny] = true;
                queue.add(new int[] {nx, ny});
            }
        }
        // BFS라 먼저 도착하면 그게 최단 거리이므로 최소값인지 여러 정답 값을 비교할 필요가 없다
        // 첫 정답값 이후 정답을 만족하는 값들은 최소값이 아니다. visited true로 적용안됨)
        return maze[n-1][m-1];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        int[][] maze = new int[n][m];
        for (int i = 0; i < n; i++) {
            String nums = br.readLine();
            for (int j = 0; j < m; j++)
                maze[i][j] = nums.charAt(j) - '0';
        }
        br.close();
        System.out.print(new Main().findMinDistance(n, m, maze));
    }
}

Python

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = []

for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().strip())))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(x, y):

    queue = deque()
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()

        for i in range(len(dx)):
            fx = x + dx[i]
            fy = y + dy[i]

            if fx <= -1 or fx >= n or fy <= -1 or fy >= m:
                continue

            if graph[fx][fy] == 0:
                continue
    
            if graph[fx][fy] == 1:
                graph[fx][fy] = graph[x][y] + 1
                queue.append((fx, fy))

    return graph[n-1][m-1]
    

print(bfs(0, 0))