백준 2178. 미로 탐색하기

문제 : 백준 2178. 미로 탐색하기

문제

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

풀이

앙 쉽다 이건.
(0, 0)부터 시작해서 (n-1, m-1)까지 이동하는 최소 거리를 구하면 된다.
(0, 0)을 큐에 넣어서 시작하고, 큐에서 pop() 하여 상하좌우에 1인 곳의 위치를 큐에 push 해주는 작업을 반복하면 된다. 다만, 방문 처리를 위한 visited[]를 생성해도 되지만 다른 문제 풀면서 특히 거리 문제 같은 경우에는 누적해서 처리해줘도 된다.
이전 x, y 의 값에서 4방향으로 움직인 좌표에 값이 1이면 아직 방문하지 않은 곳이므로 해당 위치를 방문해주면 (x, y) 까지의 이동거리에 +1을 해주면 된다.
[nx][ny] 가 0인 곳은 이동할 수 없는 곳이므로 생각할 필요가 없고, 0 또는 1이 아닌 곳은 이미 최단 이동거리가 저장되어 있으므로 방문할 필요도 없고, 값을 업데이트 해줄 필요도 없다.

풀이 코드 java

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 boj2178 {
    static int[][] a;
    static int n;
    static int m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

        a = new int[n][m];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(s.substring(j, j + 1));
            }
        }

        bfs(0, 0);
        System.out.println(a[n-1][m-1]);



    }

    static void bfs(int c, int d) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{c, d});

        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};

        while (!queue.isEmpty()) {

            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;
                if (a[nx][ny] == 1) {
                    queue.add(new int[]{nx, ny});
                    a[nx][ny] = a[x][y] + 1;
                }
            }
        }
    }
}

풀이 코드 python

from collections import deque

n, m = map(int, input().split())
graph = []
visited = [[False]*m for i in range(n)]

for i in range(n):
    graph.append(list(map(int, input())))

queue = deque()
queue.append([0, 0])
visited[0][0] = True

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

while queue:
    v = queue.popleft()
    x = v[0]
    y = v[1]

    if x == n-1 and y == m-1:
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] != 0 and not visited[nx][ny]:
                graph[nx][ny] = graph[x][y] + 1
            #if graph[nx][ny] + graph[x][y]: # 방문하지 않은 곳 노드에 추가
                queue.append([nx, ny])
                visited[nx][ny] = True
    #print(queue)
print(graph[n-1][m-1])