글 읽기 - 스타트 택시 질문있습니다.

algorithm_beginner 3년 전 0

저는 택시와 손님간의 거리가 가장 작은 값을 구하기 위해,

BFS를 이용하여, 모든 손님과 택시 간의 거리 중 가장 작은 값을 선택하는 방법으로 구현하였습니다.(작은 값이 여러개이면, 문제에서 언급한대로 구현했습니다.)

그리고 다시, 목적지까지 도착한 손님을 제외한 나머지 손님들에 대해, 위의 과정을 반복하는데, 이거 말고 좀 더 효율적으로 찾는 방법이 있을까요??

소스코드 첨부합니다.

제가 질문드린 내용과 관련있는 부분은 find_guest()함수이고 주석으로 실행코드라고 적힌 부분에 해당 함수가 호출됩니다.

감사합니다.

import sys
from collections import deque

n, m, f = map(int, sys.stdin.readline().rstrip().split())
arr = [[] for i in range(n)]
INF = int(1e9)
d = [[1,0], [-1,0], [0,1], [0,-1]]

for i in range(n):
    x = list(map(int, sys.stdin.readline().rstrip().split()))
    arr[i] = x


taxi_pos = list(map(int, sys.stdin.readline().rstrip().split()))
srcs = [[] for i in range(m)]
dsts = [[] for i in range(m)]

for i in range(m):
    src_y, src_x, dst_y, dst_x = map(int, sys.stdin.readline().rstrip().split())
    srcs[i] = [src_y, src_x]
    dsts[i] = [dst_y, dst_x]

picked = [False for _ in range(m)]


def isin(y,x):
    if -1<y<n:
        if -1<x<n: return True
    return False

# 출발지와 도착지사이의 거리와 사용된 연료 계산
def bfs(dst):
    global taxi_pos, f
    sy, sx = taxi_pos[0] - 1, taxi_pos[1] - 1
    check = [[False for _ in range(n)] for _ in range(n)]
    table = [[0 for _ in range(n)] for _ in range(n)]
    q = deque([])
    q.append([f, sy, sx])
    check[sy][sx] = True
    
    while q:
        cf, y, x = q.popleft()

        if [y, x] == [dst[0] - 1, dst[1] - 1]:

            if cf < 0: return cf, INF              

            return cf, table[y][x]

        for i in range(4):
            ny = y + d[i][0]
            nx = x + d[i][1]

            if isin(ny, nx):
                if not check[ny][nx]:
                    check[ny][nx] = True
                    if arr[ny][nx] != 1:
                        table[ny][nx] = table[y][x] + 1
                        q.append([cf-1, ny, nx])
    
    return cf, INF

# 택시와 가까운 손님을 찾는 함수
def find_guest():
    global arr, f, picked 
    dist = INF
    gpos = []
    guest_index = -1
    cf = 0

    for i in range(m):
        if not picked[i]:
            ok = False
            _cf, _dist = bfs(srcs[i])
            if _cf >= 0:
                if dist > _dist: ok = True
                
                elif dist == _dist:
                    if dist == INF: continue
                    if gpos[0] > srcs[i][0]: ok = True
                    elif gpos[0] == srcs[i][0] and gpos[1] > srcs[i][1]: ok = True
            
            if ok:
                dist = _dist
                gpos = [srcs[i][0], srcs[i][1]]
                guest_index = i
                cf = _cf

    if guest_index != -1: 
        f = cf
        picked[guest_index] = True

    return guest_index

# 손님의 목적지까지 가는 함수
def go_dst(guest_index):
    return bfs(dsts[guest_index])


# 실행코드
ok = True
cnt = m
while cnt:
    guest_index = find_guest()
    #print(guest_index)
    if guest_index == -1:
        ok = False
        break
    taxi_pos = srcs[guest_index]
    cf, dist = go_dst(guest_index)
    if cf < 0:
        ok = False
        break
    f = cf + dist * 2
    taxi_pos = dsts[guest_index]
    cnt -= 1

if ok: print(f)
else: print(-1)

algorithm_beginner 3년 전 0

손님을 찾을 때(find_guest) BFS 1번이면 되는 것을 m번을 돌려서 비효율적인 알고리즘이 됐었네요. 자문자답이긴 하지만 해결했습니다.

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

문제

문제

출처

ICPC

스타트 택시 질문있습니다.

algorithm_beginner 3년 전 0

algorithm_beginner 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말