글 읽기 - 어떤 반례가 있는지 모르겠습니다

audxo112 1년 전 0

len(queue) 를 이용하여 한타임 씩 움직이기 때문에 방문기록은 따로 안해도 되구

0 인 경우는 지금까지 몇개 부셨나를 기준으로 낮다면 이동하고

1 인 경우는 부실 수 있는지, 낮인지를 기준으로 움직입니다

질문하기, 테스트케이스, 제가 만든 테스트 케이스에선 문제가 없는데
어떤부분에서 오류가 있는걸까요 ...

import sys
from collections import deque


dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def solution(N, M, K, board):
    if N == 1 and M == 1:
        return 1

    broken = [[K + 1] * M for _ in range(N)]
    broken[0][0] = 0
    queue = deque([(0, 0)])
    time = 1
    while queue:
        time += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            k = broken[y][x]
            for (dx, dy) in dirs:
                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= M or ny < 0 or ny >= N or k >= broken[ny][nx]:
                    continue
                if board[ny][nx] == '0':
                    if (nx, ny) == (M - 1, N - 1):
                        return time
                    broken[ny][nx] = k
                    queue.append((nx, ny))
                else:
                    if k + 1 >= broken[ny][nx]:
                        continue
                    elif time % 2 == 0:
                        broken[ny][nx] = k + 1
                        queue.append((nx, ny))
                    else:
                        queue.append((x, y))
    return -1


IN, IM, IK = map(int, sys.stdin.readline().split())
IBoard = [list(sys.stdin.readline().rstrip()) for _ in range(IN)]
print(solution(IN, IM, IK, IBoard))

audxo112 1년 전 0

메모리를 최대한 적게 쓰기 위해 이전 장소의 broken 값을 가져와서 해결 하려 했는데 문제가 broken 값이 변경 되서 벽을 3개까지 부실 수 있는데 4개를 부시거나 하는 경우가 생기겠네요

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

문제

문제

출처

ICPC

어떤 반례가 있는지 모르겠습니다

audxo112 1년 전 0

audxo112 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말