[백준19238/골드2] 스타트 택시 - Python

https://www.acmicpc.net/problem/19238

 

처음에는 모든 출발지와 도착치의 좌표가 겹치는 경우가 없다고 생각해서 출발지와 목적지를 전부 mp에 대입해버렸다.

그리고 택시의 처음 위치부터 시작해서 너비우선탐색으로 가장 가까운 출발지점을 찾고, 해당 번호의 도착지를 찾은 후, 연료와 택시 위치를 갱신해서 풀었다.

그렇게 해서 1퍼센트에서 틀렸습니다 떴다.

 

# 실패 코드 1

'''
현재 위치에서 가장 가까운 손님에게 가기 (거리가 같을 경우 행번호 -> 열번호 순서로 탐색)
현재 택시와 같은 위치라면 거리 = 0
한칸 이동마다 연료 1 소모
목적지 도착시 승객 이동 중 소모한 연료의 두배 충전
이동중 연료 바닥나면 영업 종료 (도착과 동시에 연료 바닥날시에는 이동 성공)
'''

from collections import deque

N, M, fuel = map(int, input().split())
mp = [list(input().split()) for _ in range(N)]
R, C = map(int, input().split())

# 출발점과 도착점 mp에 대입 -> 앞에 출발지가 겹치는 경우 덮어 씌우면서 틀림
for c in range(M):
    si, sj, ei, ej = map(int, input().split())
    mp[si-1][sj-1] = f'{c}s'
    mp[ei-1][ej-1] = f'{c}e'

# 현재 위치 x, y에서 가장 가까운 시작점 고객 찾기
def client(x, y):
    global fuel
    q = deque([(x, y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True

    while q:
        cx, cy, cd = q.popleft()
        if mp[cx][cy] != '0' and mp[cx][cy][1] == 's':
            fuel -= cd
            return cx, cy

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < N and mp[nx][ny] != '1' and not visited[nx][ny] and cd + 1 <= fuel:
                visited[nx][ny] = True
                q.append((nx, ny, cd + 1))
	
    # 현재 연료 안에 도착 못할경우 -1 리턴
    return -1, -1

# 고객 태우고 도착점으로 이동
def move(x, y, num):
    global fuel
    q = deque([(x, y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True

    while q:
        cx, cy, cd = q.popleft()
        if mp[cx][cy] != '0' and mp[cx][cy] == f'{num}e':
            fuel += cd
            return cx, cy

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < N and mp[nx][ny] != '1' and not visited[nx][ny] and cd + 1 <= fuel:
                visited[nx][ny] = True
                q.append((nx, ny, cd + 1))
	
    # 현재 연료 안에 도착 못할경우 -1 리턴
    return -1, -1

cnt = 0
start = (R-1, C-1)

# 모든 고객을 다 이동시킬때까지 반복
while cnt < M:
    r, c = client(start[0], start[1])
    if (r, c) == (-1, -1):
        print(-1)
        exit(0)

    nr, nc = move(r, c, mp[r][c][0])
    if (nr, nc) == (-1, -1):
        print(-1)
        exit(0)
	
    # 완료한 고객 0으로 완료 표시
    mp[r][c] = '0'
    cnt += 1
    start = (nr, nc)

print(fuel)

 

 

그래서 중복되는 경우가 있을 수 도 있으니 딕셔너리에 저장하고 관리했다.

이 코드를 짜는 중간에 답이 안나왔는데, 거리가 같을 경우에 행번호가 작은것 1순위, 열번호가 작은것 2순위로 선택하는 규칙을 못지켰다.

단순히 상하좌우 탐색할 때 순서를 위-왼쪽-아래-오른쪽 순서로 순회하면 될거라고 생각했는데,

현재 위치에서 (1, -1)에 해당하는 시작점과 (0, 2)에 해당하는 시작점을 비교하면 (0, 2) 먼저 탐색해야했기 때문에 조건에 맞지않았다.

그래서 현재 위치에서 갈 수 있는 모든 시작점을 후보에 넣고, 거기서 우선순위대로 정렬하여 하나를 뽑은 후 탐색했다.

해당 시작점이 어떤 번호의 시작점인지 체크하는 방법을 index 메서드로 찾았기 떄문에 시간초과 났다.

 

# 실패 코드2

'''
현재 위치에서 가장 가까운 손님에게 가기 (거리가 같을 경우 행번호 -> 열번호 순서로 탐색)
현재 택시와 같은 위치라면 거리 = 0
한칸 이동마다 연료 1 소모
목적지 도착시 승객 이동 중 소모한 연료의 두배 충전
이동중 연료 바닥나면 영업 종료 (도착과 동시에 연료 바닥날시에는 이동 성공)
'''

from collections import deque
from heapq import heappush, heappop

N, M, fuel = map(int, input().split())
mp = [list(input().split()) for _ in range(N)]
R, C = map(int, input().split())
start = []
end = []
for c in range(M):
    si, sj, ei, ej = map(int, input().split())
    start.append((si-1, sj-1))
    end.append((ei-1, ej-1))

def client(x, y):
    global fuel
    q = deque([(x, y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True
    candidates = []

    while q:
        cx, cy, cd = q.popleft()
        if (cx, cy) in start:
           heappush(candidates, (cd, cx, cy))

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < N and mp[nx][ny] != '1' and not visited[nx][ny] and cd + 1 <= fuel:
                visited[nx][ny] = True
                q.append((nx, ny, cd + 1))

    if not candidates:
        return -1, -1
    ld, lx, ly = heappop(candidates)
    fuel -= ld
    return lx, ly

def move(x, y, num):
    global fuel
    q = deque([(x, y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True

    while q:
        cx, cy, cd = q.popleft()
        if end[num] == (cx, cy):
            fuel += cd
            return cx, cy

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < N and mp[nx][ny] != '1' and not visited[nx][ny] and cd + 1 <= fuel:
                visited[nx][ny] = True
                q.append((nx, ny, cd + 1))

    return -1, -1

cnt = 0
cur_start = (R-1, C-1)
while cnt < M:
    r, c = client(cur_start[0], cur_start[1])
    if (r, c) == (-1, -1):
        print(-1)
        exit(0)

    idx = start.index((r, c))

    nr, nc = move(r, c, idx)
    if (nr, nc) == (-1, -1):
        print(-1)
        exit(0)

    start[idx] = ""
    cnt += 1
    cur_start = (nr, nc)

print(fuel)

 

그래서 이번에는 시작점을 딕셔너리로 관리하면서 번호를 value로 지정해주고, pop으로 바로 몇번인지 찾아냈다.

 

 

# 성공 코드 1

'''
현재 위치에서 가장 가까운 손님에게 가기 (거리가 같을 경우 행번호 -> 열번호 순서로 탐색)
현재 택시와 같은 위치라면 거리 = 0
한칸 이동마다 연료 1 소모
목적지 도착시 승객 이동 중 소모한 연료의 두배 충전
이동중 연료 바닥나면 영업 종료 (도착과 동시에 연료 바닥날시에는 이동 성공)
'''

# python 36776 KB, 264 ms

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop

N, M, fuel = map(int, input().split())
mp = [list(input().split()) for _ in range(N)]
R, C = map(int, input().split())
start = {}
end = []
for c in range(M):
    si, sj, ei, ej = map(int, input().split())
    start[(si - 1, sj - 1)] = c
    end.append((ei-1, ej-1))

def client(x, y):
    global fuel
    q = deque([(x, y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True
    candidates = []

    while q:
        cx, cy, cd = q.popleft()
        if (cx, cy) in start:
           heappush(candidates, (cd, cx, cy))

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < N and mp[nx][ny] != '1' and not visited[nx][ny] and cd + 1 <= fuel:
                visited[nx][ny] = True
                q.append((nx, ny, cd + 1))

    if not candidates:
        return -1, -1
    ld, lx, ly = heappop(candidates)
    fuel -= ld
    return lx, ly

def move(x, y, num):
    global fuel
    q = deque([(x, y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True

    while q:
        cx, cy, cd = q.popleft()
        if end[num] == (cx, cy):
            fuel += cd
            return cx, cy

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < N and mp[nx][ny] != '1' and not visited[nx][ny] and cd + 1 <= fuel:
                visited[nx][ny] = True
                q.append((nx, ny, cd + 1))

    return -1, -1

cnt = 0
cur_start = (R-1, C-1)
while cnt < M:
    r, c = client(cur_start[0], cur_start[1])
    if (r, c) == (-1, -1):
        print(-1)
        exit(0)

    idx = start.pop((r, c))

    nr, nc = move(r, c, idx)
    if (nr, nc) == (-1, -1):
        print(-1)
        exit(0)

    start[idx] = ""
    cnt += 1
    cur_start = (nr, nc)

print(fuel)

 

 

문제를 풀고 보니 모든 시작점을 다 넣어줄 필요가 없는 것 같아서 리팩토링했다.

가장 가까운 시작점을 찾을 때도 최소 거리를 지정해두고 그것보다 큰 시작점은 append 하지 않는 것으로 관리하고,

최소 거리보다 더 낮은 거리가 나오면 배열도 초기화해줬다.

 

# 성공 코드 2

'''
현재 위치에서 가장 가까운 손님에게 가기 (거리가 같을 경우 행번호 -> 열번호 순서로 탐색)
현재 택시와 같은 위치라면 거리 = 0
한칸 이동마다 연료 1 소모
목적지 도착시 승객 이동 중 소모한 연료의 두배 충전
이동중 연료 바닥나면 영업 종료 (도착과 동시에 연료 바닥날시에는 이동 성공)
'''

# python 36776 KB, 132 ms

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop

N, M, fuel = map(int, input().split())
mp = [list(input().split()) for _ in range(N)]
R, C = map(int, input().split())
start = {}
end = []

# 출발지와  도착지 배열 저장
for c in range(M):
    si, sj, ei, ej = map(int, input().split())
    start[(si - 1, sj - 1)] = c
    end.append((ei-1, ej-1))

# 출발지 손님 찾기
def client(x, y):
    global fuel
    q = deque([(x, y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True
    candidates = []
    min_d = float('inf')

    while q:
        cx, cy, cd = q.popleft()

        if (cx, cy) in start:
            if cd < min_d:  # 최단 거리 갱신 시 후보 초기화
                min_d = cd
                candidates = [(cd, cx, cy)]
            elif cd == min_d:  # 같은 거리면 후보 리스트에 추가
                heappush(candidates, (cd, cx, cy))

        if cd > min_d:  # 이미 더 긴 거리면 탐색 중단
            break

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < N and mp[nx][ny] != '1' and not visited[nx][ny] and cd + 1 <= fuel and cd + 1 <= min_d:
                visited[nx][ny] = True
                q.append((nx, ny, cd + 1))

    if not candidates:
        return -1, -1
    ld, lx, ly = heappop(candidates)
    fuel -= ld
    return lx, ly

# 도착지로 이동
def move(x, y, num):
    global fuel
    q = deque([(x, y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True

    while q:
        cx, cy, cd = q.popleft()
        if end[num] == (cx, cy):
            fuel += cd
            return cx, cy

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < N and mp[nx][ny] != '1' and not visited[nx][ny] and cd + 1 <= fuel:
                visited[nx][ny] = True
                q.append((nx, ny, cd + 1))

    return -1, -1

cnt = 0
cur_start = (R-1, C-1)

# 모든 손님 다 태울때까지 반복
while cnt < M:
    r, c = client(cur_start[0], cur_start[1])
    if (r, c) == (-1, -1):
        print(-1)
        exit(0)

    idx = start.pop((r, c))

    nr, nc = move(r, c, idx)
    if (nr, nc) == (-1, -1):
        print(-1)
        exit(0)

    cnt += 1
    cur_start = (nr, nc)

print(fuel)

 

 

 

 

리팩토링하면서 시간이 반절 단축됐다. 기쁘다~