글 읽기 - 파이썬 5%에서 틀렸다는데 반례를 못찾겠습니다.

wlsrb7577 2년 전 0

테스트케이스하고 질문 검색에 있는 15개의 테스트 케이스 다 통과하는데 어느 부분에서 틀린지 아직도 못찾겠습니다..

코드 주석은 달아놓았습니다. 반례 알려주실분 계신가요..

from collections import deque
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
maps = [ list(input().rstrip()) for _ in range(n) ]
answer = -1

q = deque()

for i in range(n):
    """ "고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다."
    라는 조건이 있으므로 물을 먼저 BFS 탐색을 시키고 그 다음 고슴도치를 BFS 탐색시키면 될 것이다. """
    for j in range(m):
        if maps[i][j] == '*':
            q.append((i, j))

    for j in range(m):
        if maps[i][j] == 'S':
            maps[i][j] = 0 # 고슴도치가 이동하는 시간을 세기 위해 고슴도치의 위치를 0으로 초기화 해준다.
            q.append((i, j))

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]

while q:
    px, py = q.popleft()

    for k in range(4):
        mx = px + dx[k]
        my = py + dy[k]

        if 0 <= mx < n and 0 <= my < m:
            if maps[mx][my] == '.': # 만약 이동할 곳이 비어있는 곳이라면
                if maps[px][py] == '*': # 현재 BFS를 탐색하고 있는 것이 물이라면
                    maps[mx][my] = '*' # 이동할 곳을 물로 채워 준다.
                    q.append((mx, my))
                else: # 현재 BFS를 탐색하고 있는 것이 고슴도치 라면
                    maps[mx][my] = maps[px][py] + 1 # 이동할 곳을 +1을 해줌으로써 시간을 세어준다.
                    q.append((mx, my))

            elif maps[mx][my] == 'D': # 도착지점에 도착했다면
                if maps[px][py] != '*': # 현재 BFS를 탐색하고 있는 것이 물이 아니라면 = 고슴도치 라면
                    answer = maps[px][py] + 1 # 시간을 세고 정답 변수에 값을 대입한 후 BFS를 종료한다.
                    break

if answer == -1:
    print("KAKTUS")
else:
    print(answer)

jasminema 1년 전 0

벽은 'X'라는 조건도 써줘야합니다

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

문제

문제

출처

ICPC

파이썬 5%에서 틀렸다는데 반례를 못찾겠습니다.

wlsrb7577 2년 전 0

jasminema 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말