[김태원 알고리즘] 미로의 최단거리 통로 (BFS)

사용 언어: Python3

문제

풀이

내 풀이 - DFS 이용

dx, dy = [0,-1,0,1], [1,0,-1,0]
def DFS(x, y, cnt):
    global mn
    if (x, y) == (N-1, N-1):
        mn = min(mn, cnt)
    else:
        for w in range(4):
            xx, yy = x+dx[w], y+dy[w]
            if xx<0 or xx>=N or yy<0 or yy>=N:
                continue
            if board[xx][yy] == 1 or visited[xx][yy] == 1:
                continue
            visited[xx][yy] = 1
            DFS(xx, yy, cnt+1)
            visited[xx][yy] = 0

N = 7 # 7*7 격자판
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

mn = 2147000000
DFS(0, 0, 0)
print([mn, -1][mn == 2147000000])

• 정답!

다른 풀이 - BFS 이용

from collections import deque

N = 7 # 7*7 격자판
board = [list(map(int, input().split())) for _ in range(N)]
dist = [[0] * N for _ in range(N)] # ✅ 출발지로부터 거리
visited = [[0] * N for _ in range(N)]

q = deque()
q.append((0, 0)) # 출발 지점
visited[0][0] = 1

dx, dy = [0,-1,0,1], [1,0,-1,0]
while q:
    cur = q.popleft()
    for w in range(4):
        xx, yy = cur[0]+dx[w], cur[1]+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 1 or visited[xx][yy] == 1:
            continue
        q.append((xx, yy))
        visited[xx][yy] = 1
        dist[xx][yy] = dist[cur[0]][cur[1]] + 1

print([dist[N-1][N-1], -1][dist[N-1][N-1] == 0]) # ✅ 컨디션이 참(True)이면 리스트 1번째 요소, 거짓(False)이면 0번째 요소 반환

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기