미로 탐색

풀이

 bfs 최단 거리 문제다. 기본적인 bfs 코드에서 다음 노드로 갈 때 이전 노드의 count 값에다가 1을 더한 값을 넘기는 로직만 추가하면 된다.

시간복잡도 : O(NM)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static char[][] graph;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static int BFS(int x, int y){
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        boolean[][] visited = new boolean[N][M];
        visited[x][y] = true;
        int dist = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size-->0){
                Point curPoint = queue.poll();
                int curX = curPoint.x;
                int curY = curPoint.y;
                if (curX == N-1 && curY == M-1){
                    return dist;
                }
                for(int i=0; i<4; i++){
                    int nx = curX + dx[i];
                    int ny = curY + dy[i];
                    if(0<=nx && nx<N && 0<= ny && ny<M){
                        if (graph[nx][ny]=='1' && visited[nx][ny]==false){
                            visited[nx][ny] = true;
                            queue.offer(new Point(nx, ny));
                        }
                    }
                }
            }
            dist ++;

        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new char[N][M];
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<str.length(); j++){
                graph[i][j] = str.charAt(j);
            }
        }

        bw.write(String.valueOf(BFS(0, 0)));
        bw.flush();
        bw.close();
        br.close();
    }
}

Python

from collections import deque
N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))
visited = [[False]*M for _ in range(N)]

# 동 서 남 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0 ,0]
def bfs():
    queue = deque([(0,0,1)])
    visited[0][0] = True

    while(queue):
        x,y,c = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx == N-1 and ny ==M-1:
                print(c+1)
                return
            if 0<=nx<N and 0<=ny<M:
                if graph[nx][ny]==1 and visited[nx][ny] ==False:
                    visited[nx][ny] = True
                    queue.append((nx,ny,c+1))

bfs()