[모각코] 210807 Today I Learned

2178번: 미로 탐색 (acmicpc.net)

2178번: 미로 탐색

 

지난 문제(https://amor-fati.tistory.com/41)는 아직 해결하지 못 했다 ..... 그래서 dfs, bfs 알고리즘을 떠올릴겸 기본적인 미로 탐색 문제를 다시 풀어봤다. 풀면서 생각해보니 깊이 우선 탐색이 아니라 너비 우선 탐색으로 풀어야 했나 싶다. 그거 다 고치고 올리면 또 늦어질 것 같아서 일단 먼저 올린다. ㅜ

 

먼저 한 행씩 문자열로 입력 받은 것을 한 글자씩 읽으며 L 리스트에 저장해주고, 그 L 리스트를 maze 리스트에 넣어주어 미로를 완성했다. 굳이 리스트 안에 리스트로 하지 않아도 되지만 그냥 난 이중 리스트 형태로 미로를 만들었다. 너비 우선 탐색으로 오른쪽, 위쪽, 위쪽, 아래쪽으로 이동하면서 이동할 경우 이동하기 전의 위치값에 1을 더해 현재 위치값을 visited에 저장해주었다. (처음 시작 위치값은 1) 마지막 행, 마지막 열에 도달하면 그때 위치값이 경로의 길이가 된다.

 

(※ input n, m 반대로 받음)

import copy

m, n = map(int, input().split())    # m: 행, n:열
maze = []   #미로
for i in range(m):
    L = []
    line = input()     #한 줄 받기
    for j in range(n):
        L.append(int(line[j]))
    maze.append(L)

class Location:
    def __init__(self, row=0, col=0):
        self.row = row
        self.col = col    

def findPath(maze, m, n, v, visited):
    Q = []
    Q.append(v)
    visited[v.row][v.col] = 1
    next = Location()

    while len(Q) != 0:
        u = Q.pop(0)

        if u.row == m-1 and u.col == n-1:
            return visited[u.row][u.col]
        if u.col < n-1:     #오른쪽 이동
            if maze[u.row][u.col+1] == 1 and visited[u.row][u.col+1] == 0: 
                next.row = u.row
                next.col = u.col + 1
                visited[next.row][next.col] = visited[u.row][u.col] + 1
                Q.append(copy.deepcopy(next))
        if u.row < m-1:     #아래쪽 이동
            if maze[u.row+1][u.col] == 1 and visited[u.row+1][u.col] == 0: 
                next.row = u.row + 1
                next.col = u.col
                visited[next.row][next.col] = visited[u.row][u.col] + 1
                Q.append(copy.deepcopy(next))
        if u.col > 0:     #왼쪽 이동
            if maze[u.row][u.col-1] == 1 and visited[u.row][u.col-1] == 0: 
                next.row = u.row
                next.col = u.col - 1
                visited[next.row][next.col] = visited[u.row][u.col] + 1
                Q.append(copy.deepcopy(next))
        if u.row > 0:     #위쪽 이동
            if maze[u.row-1][u.col] == 1 and visited[u.row-1][u.col] == 0: 
                next.row = u.row - 1
                next.col = u.col
                visited[next.row][next.col] = visited[u.row][u.col] + 1
                Q.append(copy.deepcopy(next))

v = Location()               
visited = [[0 for j in range(n)] for i in range(m)]
print(findPath(maze, m, n, v, visited))