글 읽기 - Python 풀이 틀립니다 도와주세요ㅠ

jiho527 3년 전 0

예제랑 질문게시판 반례도 다 통과하고 여러가지 조건도 참고해서 짠 코드인데 틀리네요 ㅜㅜㅜ

어디가 틀렸는지 잘 모르겠습니다. 도와주세요 !!

from collections import deque
import heapq
import sys
dy = [0, 0, 1, -1]
dx = [-1, 1, 0, 0]
n, m, fuel = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            arr[i][j] = -1  # 벽을 -1로 바꾸기
y, x = map(int, input().split())
y -= 1
x -= 1
dest = [[] for _ in range(m + 1)]  # 각 승객의 목적지 배열
for i in range(m):
    y1, x1, y2, x2 = map(int, input().split())
    arr[y1 - 1][x1 - 1] = i + 1
    dest[i + 1] = [y2 - 1, x2 - 1]
def move(my, mx, idx, mc):  # 목적지까지 이동하는 함수
    move_visited = [[False] * n for _ in range(n)]
    move_visited[my][mx] = True
    q = deque([(my, mx, mc)])
    while q:
        my, mx, mc = q.popleft()
        for i in range(4):
            ny, nx = my + dy[i], mx + dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                if not (move_visited[ny][nx]): # 방문하지 않았을 경우
                    if arr[ny][nx] != -1: # 벽이 아닐경우
                        if [ny, nx] == dest[idx] : # 목적지일 경우
                            return (ny, nx, mc+1)
                        move_visited[ny][nx] = True # 방문 표시
                        q.append((ny, nx, mc+1)) # 큐에 넣기
    return -1 # 목적지를 못찾는 경우
def bfs(by, bx, bc): # 승객을 찾는 함수
    bfs_visited = [[False] * n for _ in range(n)]
    q = deque([(by, bx, bc)])
    bfs_visited[by][bx] = True
    close = [] # 승객을 담는 배열 -> 힙에 담을 예정
    while q:
        by, bx, bc = q.popleft()
        for i in range(4):
            ny, nx = by + dy[i], bx + dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                if not (bfs_visited[ny][nx]): # 방문 안했으면
                    if arr[ny][nx] != -1: # 벽이 아니면
                        bfs_visited[ny][nx] = True
                        q.append((ny, nx, bc + 1))
                        if arr[ny][nx] > 0: # 승객 발견
                            heapq.heappush(close, (bc + 1, ny, nx)) # 힙에 넣어주기 (거리, 행, 열) 순으로
    if close: # 승객이 있으면
        return close[0] # 가장 가까운 승객 return
    else: # 승객 없으면
        return -1
while True :
    if arr[y][x] > 0:  # 기사와 승객이 같은 공간에 있을 때/ 다른 승객의 목적지가 출발지일때
        result = move(y, x, arr[y][x], 0)
        if result == -1: # 목적지까지 갈 수 없을 때
            print(-1)
            sys.exit()
        if fuel < result[2]: # 목적지까지의 거리가 연료보다 크면
            print(-1)
            sys.exit()
        fuel += result[2]
        arr[y][x] = 0 # 배열에서 승객 지워주기
        y, x = result[0], result[1] # 승객의 목적지부터 다시 시작
        continue
    result2 = bfs(y, x, 0)  # 승객 찾기
    if result2 == -1: # 찾은 승객이 없으면
        if i in range(n) :
            if j in range(n) :
                if arr[i][j] > 0: # 방문안한 승객이 있을 경우
                    print(-1)
                    sys.exit()
        print(fuel) # 다 방문했으면 남은 연료 출력
        sys.exit()
    if result2[0] >= fuel: # 연료보다 승객까지의 거리가 크면
        print(-1)
        sys.exit()
    else:
        fuel -= result2[0]
        y, x = result2[1], result2[2] # 승객의 위치부터 다시 시작

jiho527 3년 전 2

while True로 푸니까

m번 돌고나서 승객을 못찾는 경우와 m번도 돌기전에 승객을 못찾았을 경우를 구분하지 못해서 틀렸습니다.

for문을 사용해서 m번 돌리되, 그 안에 (승객 찾기 + 목적지까지 이동)하는 함수를 넣어서 해결되었습니다.

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

문제

문제

출처

ICPC

Python 풀이 틀립니다 도와주세요ㅠ

jiho527 3년 전 0

jiho527 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말