글 읽기 - 65% 시간초과 질문이요.. (정답 코드 주의)

cd2420 2년 전 0

제 코드로 정답 체크하면 65%에서 시간초과가 뜹니다...

제 코드와 정답 코드 차이는 if bricked[nx][ny] > bricks 와 if bricked[nx][ny] == 1e9 비교하는 부분인데,

저는 어떻게 하다보니 맞췄지만 사실 아직 이 두 조건문 차이로 인해 왜 시간초과가 뜨는지 잘 모르겠습니다.

혹시 왜 시간초과가 뜨는 이유라든지, 제 코드로 시간초과 뜨는 반례 하나만 알려주실 수 있으실까요??

# 제 코드
import heapq
import sys

input = sys.stdin.readline
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def dkstra(x, y):
    q = []
    bricked[x][y] = 0
    heapq.heappush(q, (0, x, y))

    while q:
        bricks, x, y = heapq.heappop(q)

        if x == n - 1 and y == m - 1:
            continue

        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m:
                if bricked[nx][ny] > bricks:
                    tmp_bricks = bricks
                    if graph[nx][ny] == 1:
                        tmp_bricks += 1
                    bricked[nx][ny] = tmp_bricks
                    heapq.heappush(q, (tmp_bricks, nx, ny))


m, n = map(int, input().split())
graph = [list(map(int, list(input().rstrip()))) for _ in range(n)]
bricked = [[1e9] * m for _ in range(n)]

dkstra(0, 0)
print(bricked[-1][-1])

# 정답코드
import heapq
import sys

input = sys.stdin.readline
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def dkstra(x, y):
    q = []
    bricked[x][y] = 0
    heapq.heappush(q, (0, x, y))

    while q:
        bricks, x, y = heapq.heappop(q)

        if x == n - 1 and y == m - 1:
            continue

        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m:
                if bricked[nx][ny] == 1e9:
                    tmp_bricks = bricks
                    if graph[nx][ny] == 1:
                        tmp_bricks += 1
                    bricked[nx][ny] = tmp_bricks
                    heapq.heappush(q, (tmp_bricks, nx, ny))


m, n = map(int, input().split())
graph = [list(map(int, list(input().rstrip()))) for _ in range(n)]
bricked = [[1e9] * m for _ in range(n)]

dkstra(0, 0)
print(bricked[-1][-1])

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

문제

문제

출처

ICPC

65% 시간초과 질문이요.. (정답 코드 주의)

cd2420 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말