글 읽기 - 스타트와 택시 시간복잡도 계산을 제가 잘못한건가 궁금합니다!

iopengom 2년 전 0

N*N 배열이고 N은 최대 20 입니다.

while 손님 수 => 총 400번

find_guest -> 손님찾기 bfs (최대 400번 * 4(사방) = 1600?)

목적지 찾기 bfs (최대 400번 * 4(사방) = 1600?)

이렇게 하면 총 400 * (1600+1600) = 1,280,000 이렇게 나오는데

시간초과 판정이 나네요

시간 복잡도 계산이 틀린가요?

from collections import deque
from copy import deepcopy
N, M, fuel = map(int, input().split())
Map = [list(map(int, input().split())) for _ in range(N)]
taxi_x, taxi_y = map(int, input().split())
taxi = [taxi_x-1, taxi_y-1]
guest = []
for i in range(M):
    tmp = list(map(int, input().split()))
    x1,y1,x2,y2 = tmp
    Map[x1-1][y1-1] = i+3 # 출발지
    Map[x2-1][y2-1] = -1 # 목적지
    guest.append([x1-1, y1-1, x2-1, y2-1]) # 다 변경해주기
dx,dy = [-1,0,1,0],[0,-1,0,1]


def find_guest():
    global fuel, Map, taxi
    tMap = deepcopy(Map)
    q = deque()
    q.append([taxi[0], taxi[1], 0])
    tMap[taxi[0]][taxi[1]] = 1
    candi_guest = []
    minimum_distance = 401
    while q:
        x, y, d = q.popleft()
        not_minimum = False
        for w in range(4):
            nx, ny = x+dx[w], y+dy[w]
            if 0<=nx<N and 0<=ny<N and tMap[nx][ny] != 1: # 벽, 방문 만아니면 다 가능
                if fuel-(d+1) <= 0:# 연료 고갈
                    return []
                if tMap[nx][ny] >= 3: # 출발지 이다.
                    if minimum_distance == 401: minimum_distance = d+1
                    if d+1 > minimum_distance:
                        not_minimum = True
                        break
                    candi_guest.append([nx, ny])
                q.append([nx, ny, d + 1])
                tMap[nx][ny] = 1 # 이거 뒤에 하지 않으면 앞에 비교문 안돌아감
        if not_minimum == True:
            break

    if candi_guest:
        candi_guest.sort()
        return [candi_guest[0][0], candi_guest[0][1], minimum_distance]
    else:
        return []


def go_to_destination(dest_x, dest_y):
    global fuel, Map, taxi
    tMap = deepcopy(Map)
    q = deque()
    q.append([taxi[0], taxi[1], 0]) # x,y,거리
    while q:
        x, y, d = q.popleft()
        for w in range(4):
            nx, ny = x + dx[w], y+dy[w]
            if 0<=nx<N and 0<=ny<N and tMap != 1:
                q.append([nx, ny, d+1])
                tMap[nx][ny] = 1
                if fuel-(d+1) <= 0 and nx != dest_x and ny != dest_y: # 면료 고갈
                    return 0
                if nx == dest_x and ny == dest_y: # 목적지
                    # 전역변수 바꿔주기
                    Map[nx][ny] = 0
                    taxi = [nx, ny]
                    # 연료 두배 채우기
                    fuel += (d+1)*2
                    return d+1

#코드시작
guest_cnt = M
while guest_cnt > 0:
    result = find_guest()
    if result:
        nx, ny, d = result
        taxi = [nx,ny] # 택시 위치 옮기기

        # 도착지 알아내기
        guest_i = Map[nx][ny] - 3

        Map[nx][ny] = 0  # 출발지 사람 없애기
        fuel -= d # 연료줄이기
    else: # 연료고갈 / 목적지 못찾음
        break

    result2 = go_to_destination(guest[guest_i][2], guest[guest_i][3])
    if result2 > 0:
        fuel -= result2
        guest[guest_i] = [0,0,0,0]
        guest_cnt -= 1
    else:
        break

if guest_cnt > 0:
    print(-1)
else:
    print(fuel)

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

문제

문제

출처

ICPC

스타트와 택시 시간복잡도 계산을 제가 잘못한건가 궁금합니다!

iopengom 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말