글 읽기 - [파이썬] 시작하자마자 틀렸다고 합니다. 반례좀 알려주세요 ㅠ

sonam777 2년 전 0

bfs로 풀었고, 예제는 다 맞았습니다

from collections import deque

N, M, K = map(int, input().split())
board = [list(map(int, input())) for _ in range(N)]
vi = [[0] * M for _ in range(N)]
vi[0][0] = 1
Q = deque([[0, 0, 0]])
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
while Q:
    y, x, b = Q.popleft()
    for d in range(4):
        wy = y + dy[d]
        wx = x + dx[d]
        if 0 <= wy < N and 0 <= wx < M and not vi[wy][wx]:
            t = b
            if board[wy][wx]:
                t += 1
            vi[wy][wx] = 1 + vi[y][x]
            if t <= K:
                Q.append([wy, wx, t])

if not vi[-1][-1]:
    vi[-1][-1] = -1
print(vi[-1][-1])

skqlck 2년 전 0

4 2 1

출력 = -1

정답 = 5

그래프를 탐색하는 방향에 따라서 (상,하,좌,우 or 하,좌,상,우 or ...) 벽을 덜 깨고 도달할 수 있는 지점이 벽을 더 깨고 도달하게 됩니다.

위 예시에서 0,0 -> 0,1 -> 1,1-> 2,2의 순서로 큐에 삽입되는데 2,2는 0,1에서 파생된것으로 벽을 하나 부수고 도달한 것으로 간주됩니다. 벽을 안부수고 도달할 수 있는데 말이죠.

이로 인해 앞으로 벽을 못부수게 되서 -1을 출력하게 됩니다.

반례는 들고 왔는데 저도 어떻게 해야할지 모르겠네요. 벽 개수마다 다 방문처리한다면 시간초과가 나는데... 저도 도와주세요ㅠㅠ

sonam777 2년 전 0

반례 감사드립니다.. 저때 못풀어서 구글링해봤는데 풀이는 많더라구요... BFS로 짤때 저런 부분도 고려해야겠네요

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

문제

문제

출처

ICPC

[파이썬] 시작하자마자 틀렸다고 합니다. 반례좀 알려주세요 ㅠ

sonam777 2년 전 0

skqlck 2년 전 0

sonam777 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말