[백준 실1] 미로 탐색 (bfs/python, java)

문제

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

접근 방법

1. grid의 1부분은 접근할 수 있는 칸이다. 1을 큰 값인 int(1e9)로 초기화한다.
2. 최단거리 찾을땐 dfs보다 bfs가 더 빠르다.

코드

파이썬

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    visit = [[False for _ in range(c)] for _ in range(r)]
    q = deque()
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q.append((0, 0))
    while q:
        x, y =q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < r and 0 <= ny < c and not visit[nx][ny] and grid[nx][ny]==int(1e9):
                
                visit[nx][ny]=True
                grid[nx][ny] = min(grid[x][y]+1, grid[nx][ny])
                q.append((nx, ny))
    #print(grid)        
                
    

if __name__ == "__main__":
    r, c = map(int, input().split())
    grid = []
    for _ in range(r):
        grid.append(list(map(int, input().rstrip())))
    for i in range(r):
        for j in range(c):
            if i==0 and j==0: grid[0][0] = 1
            elif grid[i][j]:
                grid[i][j] = int(1e9)
    bfs()
    print(grid[-1][-1])

자바

https://wiselog.tistory.com/163