2178 - 미로 탐색

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

2178번: 미로 탐색

 

- BFS

 

import sys
input = sys.stdin.readline

from collections import deque

n, m = map(int, input().split())

maze = list()
for _ in range(n):
    maze.append([int(i) for i in input().strip()])

bfs = [[1,0],[0,1],[-1,0],[0,-1]]
visited = [[False] * m for _ in range(n)]
predecessor = [[None] * m for _ in range(n)]

q = deque([[0,0]])
visited[0][0] = True 
while len(q) != 0:
    k = q.pop()
    for i in range(4):
        if 0 <= k[0] + bfs[i][0] < n and 0 <= k[1] + bfs[i][1] < m:
            if visited[k[0] + bfs[i][0]][k[1] + bfs[i][1]] == False and maze[k[0] + bfs[i][0]][k[1] + bfs[i][1]] == 1:
                q.appendleft([k[0] + bfs[i][0],k[1] + bfs[i][1]])
                visited[k[0] + bfs[i][0]][k[1] + bfs[i][1]] = True
                predecessor[k[0] + bfs[i][0]][k[1] + bfs[i][1]] = [k[0],k[1]]

cnt = 1
value = predecessor[n-1][m-1]
while value != predecessor[0][0]:
    cnt += 1
    value = predecessor[value[0]][value[1]]

print(cnt)

 

저번에 공부한 거 바탕으로 풀었는데 코드가 그닥 깔끔하지는 않다

변수 생성해서 bfs 할 때 인덱스 길이를 좀 줄였으면 어땠을까 하는 생각이 든다

 

문제 해결 아이디어는.. bfs 연산 돌려서 predecessor에 전(前) 좌표를 기록하고, 다시 쭉 따라가면서 1씩 더해줬다.

 

근데 풀고 다른 사람들 코드 확인하는데, 굳이 predecessor 리스트에 전(前) 좌표를 기록하기보단 그냥 1씩 더해줘도 최단 경로의 길이는 구할 수 있었다

 

 

코드 참고해서 다르게 풀어봤다 리팩토링도 좀 하고..

import sys
input = sys.stdin.readline

from collections import deque

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

bfs = [[1,0],[0,1],[-1,0],[0,-1]]
visited = [[False] * m for _ in range(n)]
predecessor = [[1] * m for _ in range(n)]

q = deque([[0,0]])
visited[0][0] = True 

while len(q) != 0:
    r, c = q.pop()
    for dr, dc in bfs:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < n and 0 <= nc < m:
            if visited[nr][nc] == False and maze[nr][nc] == 1:
                q.appendleft([nr,nc])
                visited[nr][nc] = True
                predecessor[nr][nc] = predecessor[r][c] + 1

print(predecessor[n-1][m-1])

 

훠얼씬 보기 좋은 코드가 됐다!

 

보니까 어떤 사람은 maze 리스트에 있는 값을 1씩 증가시켜서 visited 리스트도 안 만들고 사용하던데.. 되게 좋은 아이디어 같았다

 

그리고 map(int, input().rstrip()) 쓰면 (문자열) 123456으로 들어와도 (정수형) 1,2,3,4,5,6으로 바뀌는 거 처음 알았다

띄어쓰기 없어서 안될 줄 알았는데 되더라궁..

 

그리고 인자 두 개씩 받아보니까 되게 간편하다! 앞으로 많이 쓸 예정