[백준/파이썬] 2655 미로만들기

#문제링크

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

2665번: 미로만들기

#나의풀이

import sys
from heapq import heappush, heappop

delta = [[1, 0], [0, 1], [-1, 0], [0, -1]]

if __name__=="__main__":
    N = int(sys.stdin.readline())
    board = []
    for _ in range(N):
        board.append(list(map(int, sys.stdin.readline().rstrip())))

    visited = [[0]* N for _ in range(N)]
    heap = []
    heappush(heap, [0, 0, 0])
    visited[0][0] = 1

    while(heap):
        tmp = heappop(heap)
        if tmp[1] == N-1 and tmp[2] == N-1:
            print(tmp[0])
            exit(0)
        for i in range(4):
            dx = tmp[1] + delta[i][0]
            dy = tmp[2] + delta[i][1]
            if 0 <= dx < N and 0 <= dy < N and visited[dx][dy] == 0:
                visited[dx][dy] = 1
                if board[dx][dy] == 0:
                    heappush(heap, [tmp[0]+1, dx, dy])
                else:
                    heappush(heap, [tmp[0], dx, dy])

#해설

visited = [[0]* N for _ in range(N)]
    heap = []
    heappush(heap, [0, 0, 0])
    visited[0][0] = 1

방문했는지 체크하기 위해 visited 2차원 배열을 입력과 똑같이 만들어주었다. 0일때는 방문하지 않은것이고 1이 되면 방문한것으로 사용할것이다.

여기서는 heap을 사용했다. 첫번째 값에 부순 벽돌의 개수를 넣을것이고 벽돌 수가 적은 것부터 정렬하여 탐색할것이다.

0,0부터 탐색하므로 방문한것으로 바꿔주고 힙에 값을 넣어준다.

 

while(heap):
        tmp = heappop(heap)
        if tmp[1] == N-1 and tmp[2] == N-1:
            print(tmp[0])
            exit(0)
        for i in range(4):
            dx = tmp[1] + delta[i][0]
            dy = tmp[2] + delta[i][1]
            if 0 <= dx < N and 0 <= dy < N and visited[dx][dy] == 0:
                visited[dx][dy] = 1
                if board[dx][dy] == 0:
                    heappush(heap, [tmp[0]+1, dx, dy])
                else:
                    heappush(heap, [tmp[0], dx, dy])

BFS처럼 실행한다 tmp에 힙에 첫번째 값을 빼주고 넣어준다. 만약 tmp가 목표지점에 도착하면 0번째 인덱스 벽돌 부순 개수를 출력하고 프로그램을 종료시켰다.

도착하지 않았을경우 4방탐색을 한다. 이후 탐색한 위치가 배열 안인지 체크하고 방문했는지 체크한다 조건문이 맞을경우 방문처리를 해주고 만약 벽돌일경우는 0번째 인덱스에  현재 벽돌부순갯수+1 을 넣어주고 아닐경우는 그대로 넘겨준다.