3주차 과제 4.미로탐색 BEST 풀이

베스트 풀이 링크

베스트 풀이코드- genuinenameerror님

# 백준 2178번 미로 탐색 
import collections
import sys
N,M=map(int,sys.stdin.readline().split())
#houses = [list(map(int,list(input()))) for x in range(N)]
maze=[list(map(int,list(sys.stdin.readline().strip()))) for x in range(N)]
#print(maze)
visited=[[0]*(M) for x in range(N)]
#print(visited)
shortest = [[10001]*(M) for x in range(N)]
to_search = collections.deque([[0,0]])
comparison=[[-1,0],[1,0],[0,-1],[0,1]]
shortest[0][0]=1
while to_search:
    #print(to_search)
    current_loc = to_search.popleft()
    if visited[current_loc[0]][current_loc[1]]==0:
        visited[current_loc[0]][current_loc[1]]=1
        
        
    for compare in comparison:
        compare=[current_loc[0]+compare[0],current_loc[1]+compare[1]]
        #print(compare)
        if compare[0]>=0 and compare[0]<N \
           and compare[1]>=0 and compare[1]<M \
           and maze[compare[0]][compare[1]]==1 \
           and visited[compare[0]][compare[1]]==0:
            to_search.append(compare)
            visited[compare[0]][compare[1]]=1
            shortest[compare[0]][compare[1]]=shortest[current_loc[0]][current_loc[1]]+1
            
    
#print(shortest)
print(shortest[N-1][M-1])

베스트 풀이 선정 이유

코드의 가독성과 효율성이 다른 코드에 비해 좋지는 않다.
하지만 문제 풀이 전 들었던 생각을 잘 정리해서 자세히 작성해주셨기 때문에 베스트 풀이로 선정했다.
왜 이 문제가 bfs인지 몰랐지만 공부해서 알았다라는 점, 입력값을 받을 때 파이써닉한 코드

maze=[list(map(int,list(sys.stdin.readline().strip()))) for x in range(N)]

를 사용한 점, 문제를 해결하는 방법을 자세히 작성했다는 점에서 베스트 풀이로 선정했다.
또한 위 코드에서 strip()을 사용한 이유 등 코드에 대한 설명을 자세히 작성해놓았고 사소한 실수들도 작성하여 나중에 실수하지 않도록 한 점 때문에 베스트 풀이로 선정했다.

추가 코드(simyoju님이 코드 작성시 참고하신 풀이)

풀이 출처: https://gingerkang.tistory.com/40

from collections import deque
import sys

input = sys.stdin.readline

def bfs():
    q = deque()
    q.append((0, 0))
    distance = [[0] * m for _ in range(n)]
    # 시작 위치 카운트
    distance[0][0] = 1
    cnt = 1

    while q:
        x, y = q.popleft()
        for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if maze[ny][nx] == '1' and distance[ny][nx] == 0:
                distance[ny][nx] = distance[y][x] + 1
                q.append((nx, ny))

    return distance[n - 1][m - 1]

n, m = map(int, input().split())
maze = [input() for _ in range(n)]

print(bfs())

위에 풀이는 simyoju님이 코드 리뷰시 참고하신 코드입니다. 깔끔하다고 생각해서 다른 분들이 참고하면 좋을 것 같아 올렸습니다.

느낀점

bfs/dfs는 구글링을 통해 다양한 분들의 깔끔한 코드를 보고 공부하면 좋을 것 같다고 느꼈습니다.