[BOJ] 1216번 알고스팟 / 사용언어 : 파이썬(python)

※ 문제링크 

1261번: 알고스팟

해당 문제는 우선순위 큐와 BFS를 활용해서 풀 수 있는 문제였다. 간단하게 풀이방법에 대해서 설명하면, 자신의 위치에서 상,하,좌,우를 확인할 수 있는 BFS함수를 작성하고, 조건을 만족하면 우선순위큐에 해당 자료를 넣은 다음 가장 작은 값부터 출력하는 최소힙을 활용하여 원하는 위치로 이동하기 위해서 부숴야하는 벽의 개수를 카운팅해주고, 이동을 완료했을 때의 부순 벽의 개수를 출력해주면되었다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 바탕으로 미로를 2차원 배열로 구현해준다.

2. 4방위(상, 하, 좌, 우)를 탐색할 BFS함수를 작성해주고, 최소힙을 사용하여 값들을 저장하고, 가장 작은 값부터 출력할 수 있게 한다.

3. 원하는 위치에 도달하면 탐색을 중지하고 값을 출력한다.

 

import heapq
import sys

M, N = map(int, input().split()) # M: 가로길이(x좌표) / N: 세로길이(y좌표)
# M, N = map(int, sys.stdin.readline().split())
maze = []
for _ in range(N):
    sample = [int(i) for i in input()]
    # sample = [int(i) for i in sys.stdin.readline().rstrip()]
    maze.append(sample)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

visited = [[False for _ in range(M)] for _ in range(N)]
def dtw_min(x, y):
    if M == 1 and N == 1:
        return 0
    destroy = 0
    heap = []
    heapq.heappush(heap, [0, x, y])
    visited[y][x] = True

    while heap:
        dtw, x, y= heapq.heappop(heap)
        if dtw > destroy:
            destroy += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if maze[ny][nx] == 0 and dtw == destroy and visited[ny][nx] == False:
                    visited[ny][nx] = True
                    heapq.heappush(heap, [dtw, nx, ny])
                    if nx == M-1 and ny == N-1:
                        return dtw
                if maze[ny][nx] == 1 and visited[ny][nx] == False:
                    heapq.heappush(heap, [dtw+1, nx, ny])
                    visited[ny][nx] = True
                    if nx == M-1 and ny == N-1:
                        return dtw+1

print(dtw_min(0, 0))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.