글 읽기 - 19238 파이썬 7퍼에 틀렸습니다..ㅠ 반례 다 해봤어요ㅠㅠ

angly97 2년 전 0

질문글에 있는 반례 전부 다 했는데

다 통과했는데ㅠㅠㅠㅠ

왜 자꾸 7%에 틀렸다고 나올까요...???ㅠㅠㅠㅠㅠ

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

def bfs_g(cx, cy, gx, gy):
  q = deque([[cx, cy, 0]])
  field[cx][cy] = -flag

  while q:
    nx, ny, dis = q.popleft()
    if dis > fuel:    # 연료 부족할 경우 실패
      return -1
    
    if nx == gx and ny == gy:
      return dis
    
    for d in dir:
      dx = nx+d[0]; dy = ny+d[1]
      if 0<=dx<n and 0<=dy<n:
        # 승객을 찾기까지 방문 표시 = flag (bfs_c에서 사용)
        # 승객 태우고 목적지까지 가는 방문 표시 = -flag (현재 함수에서 사용)
        if field[dx][dy] != 1 and -flag < field[dx][dy] <= flag:
          field[dx][dy] = -flag
          q.append([dx, dy, dis+1])
            
# 승객 찾기 bfs
def bfs_c(x, y):
  global fuel, flag
  q = deque([[x, y, 0]])
  field[x][y] = flag
  
  while q:
    nx, ny, dis = q.popleft()

    # 연료 모두 소진할 경우 실패
    if dis == fuel:
      return [-1,-1,-1,-1,-1]

    # 현재 좌표가 승객 좌표에 해당하는 지 검사
    for i in range(len(cstm)):
      if cstm[i] == [nx, ny]:
        cstm.pop(i)                   # 현재 승객은 대기 목록에서 삭제
        gx, gy = goal.pop(i)          # 대응되는 목적지도 대기 목록에서 삭제
        return [nx, ny, gx, gy, dis]  # 승객 좌표, 목적지 좌표, 소모된 연료 

    for d in dir:
      dx = nx+d[0]; dy = ny+d[1]
      if 0<=dx<n and 0<=dy<n:
        # 승객을 찾기까지 방문 표시 = flag (현재 함수에서 사용)
        # 승객 태우고 목적지까지 가는 방문 표시 = -flag (bfs_g에서 사용)
        if field[dx][dy] != 1 and -flag < field[dx][dy] < flag:
          field[dx][dy] = flag
          q.append([dx, dy, dis+1])
  return [-1,-1,-1,-1,-1]  # 실패할 경우

  
if __name__ == '__main__':
  n, m, fuel = map(int, input().strip().split())
  field = [list(map(int, input().strip().split())) for _ in range(n)]
  start = list(map(lambda x: int(x)-1, input().strip().split()))  # 초기 시작점
  
  cstm = []; goal = []  # cstm[i]: 손님i의 좌표, goal[i]: 손님i의 목적지
  for _ in range(m):
    a, b, c, d = map(int, input().strip().split())
    cstm.append([a-1, b-1])
    goal.append([c-1, d-1])

  # 행이 더 작은 것 먼저, 행이 같다면 열이 더 작은 것 먼저
  dir = [(-1, 0), (0, -1), (0, 1), (1, 0), ]
  
  flag = 2  # 손님 넘버(2~m+2)
  while flag < m+2 and fuel > 0:
    cx, cy, gx, gy, c_dis = bfs_c(start[0], start[1])
    if cx == -1:    # 주어진 연료로 도달할 수 있는 손님 없음
      break
    fuel -= c_dis

    g_dis = bfs_g(cx, cy, gx, gy)
    if g_dis == -1:  # 주어진 연료로 목적지 도달 불가
      break

    start = [gx, gy]  # 현 위치를 새로운 시작점으로 설정
    fuel += g_dis
    flag += 1         # 손님 넘버링 값 증가

  if flag == m+2:
    print(fuel)
  else:
    print(-1)

ksh7628 2년 전 1

행, 열 우선 순위 처리를 하시려고 69번째 라인을 작성하신거 같은데 예외가 있는 경우가 있어서 따로 정렬이나 갱신을 해주셔야 합니다.
https://www.acmicpc.net/board/...

위 링크에 다른분이 답변해주신 것처럼 예외가 있는 경우가 있습니다.

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

문제

문제

출처

ICPC

19238 파이썬 7퍼에 틀렸습니다..ㅠ 반례 다 해봤어요ㅠㅠ

angly97 2년 전 0

ksh7628 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말