글 읽기 - Python 7% 틀렷습니다. 틀린부분을 모르겠습니다.

kk0640 3년 전 0

현재 구성은 1. 승객을 찾으러가는 BFS ,2. 승객을 태우고 목적지를 가기위한 BFS로 구성하였습니다.

변수는 dict 형태로 people[(위치)]=숫자, destination[사람숫자] = (목적지) , 로 구성하였습니다.

1. 승객을 찾으러가는 BFS

현재위치,연료등을 기준으로 BFS로 탐색하며 가장 가까운 위치의 승객을 태웁니다.

이때 새롭게 이동한 위치가 people의 key에 있다면 candidate 리스트에 넣은 후 candidate 에서 정렬한 뒤 조건에 맞는 [0] idx 만 뽑아서 return 해줍니다.

만약 가야할 위치가 현재 연료보다 더 멀다면(fuel < nc) , bfs가 끝낫는데 손님이 남아있으면 -1로 return 했습니다.

2.승객을 태우고 목적지로 가기 위한 BFS

1번에서의 결과가 -1이면 바로 실행 안되고 다른 값인 경우에 실행됩니다.

똑같이 BFS를 돌리며 nx,ny가 goal에 도달하면 fuel를 더해주고 start_x,start_y 를 업데이트하며 1을 리턴해줍니다.

도저히 7%에서 틀렷습니다가 나오는 이유를 모르겠습니다.

도와주십쇼 고수님들..

from collections import deque

n,m,fuel = map(int,input().split())
maps = [list(map(int,input().split())) for _ in range(n)]
start_x,start_y = map(int,input().split())
people ={}
destination = {}

start_x-=1
start_y-=1
cnt=m

for i in range(1,m+1):
    people_x,people_y,destination_x,destination_y = map(int,input().split())
    people[(people_x-1,people_y-1)]=i
    destination[i]=(destination_x-1,destination_y-1)

def bfs_customer(cur_x,cur_y):
    global maps,people,destination,fuel,start_x,start_y
    dx = [-1,0,0,1]
    dy =[0,-1,1,0]
    visited = [[0]*n for _ in range(n)]
    dq = deque([(cur_x,cur_y,0)])
    visited[cur_x][cur_y]=1
    candidate =[]
    while(dq):
        cur_x ,cur_y,cur_c = dq.popleft()
        if((cur_x,cur_y) in people.keys()):
            fuel-=cur_c
            start_x,start_y = cur_x,cur_y
            return people[(cur_x,cur_y)]
        nc = cur_c +1
        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]
            if(nx>=n or nx<0 or ny>=n or ny<0):
                continue
            if(maps[nx][ny]==1):
                continue
            if(nc>fuel):
                return -1
            if((nx,ny) in people.keys()):
                candidate.append((nx,ny,nc))
                visited[nx][ny]=1
            if(visited[nx][ny]==0):
                visited[nx][ny]=1
                dq.append((nx,ny,nc))
        if(len(candidate)!=0):
            break
    if(candidate):
        candidate.sort(key=lambda x:(x[0],x[1]))
        fuel -= candidate[0][2]
        start_x = candidate[0][0]
        start_y = candidate[0][1]
        return people[(candidate[0][0],candidate[0][1])]
    return -1

def bfs_destination(num):
    global maps,fuel,people,destination,cnt,start_x,start_y
    cur_x ,cur_y = start_x,start_y
    dx =[1,0,-1,0]
    dy =[0,1,0,-1]
    visited = [[0] * n for _ in range(n)]
    dq = deque([(cur_x, cur_y,0)])
    visited[cur_x][cur_y] = 1
    goal_x,goal_y = destination[num]
    while(dq):
        cur_x,cur_y,cur_c = dq.popleft()
        nc = cur_c+1
        for i in range(4):
            nx=cur_x+dx[i]
            ny=cur_y+dy[i]
            if(nc>fuel):
                return -1
            if(nx>=n or nx<0 or ny>=n or ny<0):
                continue
            if(maps[nx][ny]==1):
                continue
            if((nx,ny)==(goal_x,goal_y)):
                fuel +=nc
                cnt-=1
                start_x ,start_y = goal_x,goal_y
                return 1
            if(visited[nx][ny]==0):
                visited[nx][ny]=1
                dq.append((nx,ny,nc))
    return -1

while(1):
    condition1 =bfs_customer(start_x,start_y)
    #print('cnt',cnt)
    if(cnt==0):
        #print('fuel')
        print(fuel)
        break
    if(condition1==-1):
        print(-1)
        break
    else:
        del people[(start_x,start_y)]
        condition2 = bfs_destination(condition1)
        if(condition2==-1):
            print(-1)
            break
        del destination[condition1]
        #print('start',start_x,start_y)

qjatn1009 3년 전 1

6 4 100

0 0 1 0 0 0

0 0 0 0 0 0

0 0 0 0 1 0

0 0 0 1 0 0

6 5

1 6 2 2

1 6 3 5

1 6 5 4

1 6 1 1

시작이 다같으면 답이 틀리네요

ans : 100

출력 : -1

kk0640 3년 전 0

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

모든 손님의 출발지가 달라야 하는거 아닌가요?

kk0640 3년 전 0

또한 주신 예제에서는

1출발점=2출발점=3출발점=4출발점

일때

- +

시작점--출발점 4출발점--4도착점
4도착점--4출발점 3출발점--3도착점
3도착점--3출발점 2출발점--2도착점
2도착점--2출발점 1출발점--1도착점
이므로
결국(1출발점-1도착점 거리) - (시작점-출발점 거리)가 되어서
7-6=1
따라서 ans =101이 되어야 맞지 않나요?

kk0640 3년 전 0

정답 코드에 해당 예제를 돌리면 -1이 나옵니당~

qjatn1009 3년 전 0

모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

글을 보지 못했었네요.

위 코드로는 돌리면 -1이 나오는데 출발지가 같으면 people에 값이 1개밖에 저장이 안되서 그렇습니다.

elrnwl 3년 전 3

저도 7%에서 계속 틀렸다가 "다음 손님을 찾는 로직"을 바꿨더니 통과했어요.

다음 손님을 거리>row>column 순으로 제대로 처리해줬는지 한 고려해보시는걸 추천드립니다.

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

문제

문제

출처

ICPC

Python 7% 틀렷습니다. 틀린부분을 모르겠습니다.

kk0640 3년 전 0

qjatn1009 3년 전 1

kk0640 3년 전 0

kk0640 3년 전 0

kk0640 3년 전 0

qjatn1009 3년 전 0

elrnwl 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말