글 읽기 - 2206 벽부수고이동하기 해결방식질문

alftjd1 4년 전 0

다른 사람들은 거의 다 'deque' 과 벽을 뚫었을때와 안뚫었을때를 비교하는 방식으로

문제를 해결하던데 이렇게 'heapq'을 이용하여 해결 할 수는 없는 걸까요?

from sys import stdin
import heapq
input = stdin.readline

n, m = map(int,input().rsplit())
miro = [list(map(int,input().rstrip())) for _ in range(n)] # data
graph = [['x'] * m for _ in range(n)] # wall

graph[0][0] = 0
temp = []
heapq.heappush(temp,[1,0,0])

while temp:
    #print(temp)
    l, x, y = heapq.heappop(temp)
    if x == n - 1 and y == n - 1:
        break
    for i, j in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        if 0 > x + i or x + i >= n or 0 > y + j or y + j >= m:
            continue
        if graph[x + i][y + j] != 'x':
            continue

        if not miro[x + i][y + j]:
            graph[x + i][y + j] = graph[x][y]
            heapq.heappush(temp, [l + 1, x + i, y + j])
        elif miro[x + i][y + j] and not graph[x][y]:
            graph[x + i][y + j] = graph[x][y] + 1
            heapq.heappush(temp, [l + 1, x + i, y + j])

#[print(*g) for g in graph]
if graph[-1][-1] == 'x':
    print(-1)
else:
    print(l)

hello70825 4년 전 8

heapq도 마찬가지로 벽을 뚫었을때, 안뚫었을때 인자를 추가시켜 bfs를 돌리면 통과합니다.

반례 드립니다.

6 3
000
110
000
011
111
000
    
18줄 i,j = 1,0이기 때문에 시작지점 바로 아래를 뚫고 이동해버려서 0으로 돌아서 가는 길을 찾지 못하고 종료합니다.

123
2x4
365
4xx
xxx

alftjd1 4년 전 1

감사합니다. 내일 아침에 한번 빠르게 해결해보겠습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2206 벽부수고이동하기 해결방식질문

alftjd1 4년 전 0

hello70825 4년 전 8

alftjd1 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말