글 읽기 - 파이썬 17% 에서 틀렸습니다

roy2554 1년 전 0

제가 볼때는 틀린 부분이 없는것 같은데 혹시 오류나 반례가 있으면 알려주시면 감사하겠습니다.

from heapq import heappop, heappush
import itertools

INF = float('inf')
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def solve():
    n, m = map(int, input().split())
    _map = []
    for _ in range(n):
        _map.append(list(map(int, list(input()))))

    cost = [[INF for i in range(len(_map[0]))] for j in range(len(_map))]
    cost[0][0] = 1

    pq = []

    # data type (cost, current_x, current_y, isAvailToPassWall)
    heappush(pq, (0, 0, 0, True))
    while pq:
        cur_cost, cur_x, cur_y, isAvailToPass = heappop(pq)
        for ax, ay in zip(dx, dy):
            new_x, new_y = cur_x + ax, cur_y + ay

            # 기저사례: 좌표 유효성 검사
            if new_x < 0 or new_x >= len(_map[0]) or new_y < 0 or new_y >= len(_map): continue
            # 기저사례: 새로운 좌표가 벽이고 벽울 이미 통과함
            if not isAvailToPass and _map[new_y][new_x] == 1: continue
            # 새로운 좌표가 벽이고 벽을 통과하지 않았을때
            if _map[new_y][new_x] == 1: isAvailToPass = False

            new_cost = cost[cur_y][cur_x] + 1
            if cost[new_y][new_x] > new_cost:
                cost[new_y][new_x] = new_cost
                heappush(pq, (new_cost, new_x, new_y, isAvailToPass))
      
    # itertools.chain.from_iterable -> [[1, 2, 3], [4, 5, 6]] 을 [1, 2, 3, 4, 5, 6] 으로 변환해주는 함수입니다.
    #  ㄴ> 2차원 배열을 1차원 배열로 변환
    result = list(itertools.chain.from_iterable(cost))[-1]
    if result == INF:
        return -1
    return result

if __name__ == "__main__":
    print(solve())

sinusoid500 1년 전 17

벽을 1번 뚫고 진행한 경로와 벽을 뚫지 않고 진행한 경로가 겹치는 경우에 문제가 됩니다.

아래의 반례를 통해서 이해하실 거라 생각됩니다.

---------------------------

입력

6 6
000000
011111
011111
010100
010110
000110

---------------------------

출력

-1

---------------------------

정답

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

문제

문제

출처

ICPC

파이썬 17% 에서 틀렸습니다

roy2554 1년 전 0

sinusoid500 1년 전 17

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말