Python으로 푸는 백준 2178. 미로탐색

 백준 2178. 미로탐색

문제는 N X N 으로 표현되는 2차원 배열이 있다. 

(0,0)에서 출발하여 (N-1, M-1) 위치까지 이동할 때, 지나가게 되는 칸 수의 최솟값이 무엇인지 구해야 한다.

백준에서 푼 문제 리스트 보기

github에서 코드보기

문제 조건

1은 길이고 0은 벽이다. 

서로 인접한 칸으로만 이동할 수 있다. (즉, 상하좌우로만 이동이 가능하다)

문제 풀이

모든 칸이 벽이 존재하지 않고 이동가능한 칸(1)일 경우에는 어떤 경로로 현재의 칸에 도달하게 되었는지에 따라서

거쳐온 칸 수가 서로 다를 수도 있다. 그러므로   (0,0)에서 부터 시작하여 상하좌우의 칸들이 이동가능한 칸인지 확인하고

이미 지나온 칸이더라도 이동 가능한 칸이라면  (지나온 칸 수 + 1) < (최소 칸이라고 입력되어 있는 칸 수) 일 경우에만 값을 갱신해준다.

값을 갱신 한 후에 해당 칸의 정보를 탐색 해야 하는 칸들의 대기열에 다시 넣어준다.

대기열에 들어간 칸들의 상하좌우 경로를 탐색해 나감으로써 (N-1, M-1)까지 이동 경로 상의 최소의 칸 수를 갱신해 나가는 것이다.

 탐색해야 하는 칸들의 대기열이 비워지면 맨 마지막 (N-1, M-1)에는 이 지점까지 오는데 거쳐온 최소의 칸 수가 기록되어 있다.

파이썬 코드 

 
def solve(start, goal, lines):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    next_pos = []
    next_pos.append(start)
    while next_pos:
        x, y = next_pos.pop(0)
        value = lines[x][y]
        for i in range(4):
            temp_x = x + dx[i]
            temp_y = y + dy[i]
            if temp_x < 0 or temp_y < 0 or temp_x >= n or temp_y >= m:
                continue
            
            temp_value = lines[temp_x][temp_y]
 
            # 벽은 패스
            if temp_value < 1:
                continue
 
            # 현재 진행 경로가 더 적은 VALUE일 경우
            if temp_value == 1 or value + 1 < temp_value:
                lines[temp_x][temp_y] = value + 1
                next_pos.append((temp_x, temp_y))
    return lines[goal[0]][goal[1]]
 
if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    lines = []
    for i in range(n):
        line = list(map(int, list(input().strip())))
        lines.append(line)
    start = (0, 0)
    goal = (n-1, m-1)
    print(solve(start, goal, lines))
    

#백준 2178 미로탐색 #백준 2178 미로 탐색 #백준 미로탐색 python #python 백준 2178