137. [삼성기출33]Python 백준 19238 번 스타트 택시 자세한 설명 및 반례

안녕하세요 코딩하는 덕구입니다.

파이썬 백준 19238 스타트 택시입니다.

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

19238번: 스타트 택시

백준 19238 스타트 택시 파이썬 코드입니다. 설명은 아래에 있습니다.

from collections import deque
N, M, fuel = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
x, y = map(int, input().split())
x, y = x-1, y-1
info = [list(map(int, input().split())) for _ in range(M)]
#승객 2 도착 3
index_p = {}
cord_d = {}

for num, i in enumerate(info):
    x1, y1, x2, y2 = i
    board[x1 - 1][y1 - 1] = 2
    index_p[(x1 - 1, y1 - 1)] = num
    cord_d[num] = [x2 - 1, y2 - 1]

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

def solve():
    global x, y, fuel

    while M > 0:
        x, y, fuel, destx, desty = find_passenger(x, y, fuel)
        if fuel < 0:
            return -1

        fuel = go_destination(x, y, fuel, destx, desty)
        x, y = destx, desty
        if fuel < 0:
            return -1
    return fuel

def find_passenger(x, y, fuel):
    global M
    distance = 1e9
    candidate = [] #승객 후보
    queue = deque()
    queue.append([x, y, fuel])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True

    while queue:
        x, y, fuel = queue.popleft()
        start = fuel
        if board[x][y] == 2: #도착한 경우
            if fuel >= 0:
                if start - fuel <= distance:
                    candidate.append([x, y, fuel])
                    distance = start - fuel

        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny] and board[nx][ny] != 1 and 0 < fuel:
                    visited[nx][ny] = True
                    queue.append([nx, ny, fuel - 1])

    if candidate:
        candidate.sort(key=lambda x : (-x[2], x[0], x[1]))
        x, y, fuel= candidate[0]
        board[x][y] = 0
        M -= 1
        num = index_p[(x, y)]
        destx, desty = cord_d[num]
        return [x, y, fuel, destx, desty]

    return [-1, -1, -1, -1, -1] #갈 곳이 없는 경우

def go_destination(x, y, fuel, destx, desty):
    queue = deque()
    origin = fuel
    queue.append([x, y, fuel])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True

    while queue:
        x, y, fuel = queue.popleft()
        if [x, y] == [destx, desty]:
            if fuel < 0:
                return -1
            return fuel + (origin - fuel) * 2

        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny] and board[nx][ny] != 1 and fuel > 0:
                    visited[nx][ny] = True
                    queue.append([nx, ny, fuel - 1])

    return -1

print(solve())

 

문제 접근

1. 가장 가까운 승객을 찾기위한 BFS 1번

2. 최단 거리로 도착에 가기위한 BFS 1번

3. 위의 BFS들을 연료가 떨어지거나 모든 승객을 태울 때 까지 반복합니다.

4. 최단거리의 승객이 여러명인 경우 열과 행이 가장 작은 숫자인 승객을 태웁니다.

이때 BFS탐색을 [상, 좌, 우, 하]순으로 시도하고, 가장 먼저 만난 승객을 태우게 되면

4번의 조건을 통과하지 못합니다.

[좌, 좌, 좌],  [우, 우, 상] 의 경우 1 번째 경우가 먼저 탐색이 되지만

우선순위에서 2 번째 경우가 앞서는 반례가 있습니다.

 

Python 코드 구현

그래프의 상태, 승객과, 도착지, 방향을 구현하기 위한 코드들을 작성합니다.

index_p의 경우 좌표를 넣으면 몇번 승객인지 알려주는 dictionary 입니다.

cord_d는 번호를 넣으면 도착 좌표를 알려줍니다.

from collections import deque
N, M, fuel = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
x, y = map(int, input().split())
x, y = x-1, y-1
info = [list(map(int, input().split())) for _ in range(M)]
#승객 2 도착 3
index_p = {}
cord_d = {}

for num, i in enumerate(info):
    x1, y1, x2, y2 = i
    board[x1 - 1][y1 - 1] = 2
    index_p[(x1 - 1, y1 - 1)] = num
    cord_d[num] = [x2 - 1, y2 - 1]

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

 

1. find_passenger 를 통해 조건에 맞는 최단거리 승객을 찾습니다.

2. go_destination을 통해 최단거리로 도착지로 이동한 후 연료를 채웁니다.

3. 모든 승객을 다 태울때 까지 반복합니다.

4. 이때 연료가 다 떨어지거나 승객 혹은 도착지를 찾을 수 없으면 -1 을 return 합니다.

def solve():
    global x, y, fuel

    while M > 0:
        x, y, fuel, destx, desty = find_passenger(x, y, fuel)
        if fuel < 0:
            return -1

        fuel = go_destination(x, y, fuel, destx, desty)
        x, y = destx, desty
        if fuel < 0:
            return -1
    return fuel

print(solve())

 

조건에 맞는 최단거리의 승객을 찾는 함수 find_passenger입니다.

candidate는 승객 후보를 담는 list입니다.

승객을 찾게되면 기존보다 distance가 크지 않은지 확인 한 후, distance를 업데이트 합니다.

조건에 맞다면 cansdidate에 추가합니다.

def find_passenger(x, y, fuel):
    global M
    distance = 1e9
    candidate = [] #승객 후보
    queue = deque()
    queue.append([x, y, fuel])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True

    while queue:
        x, y, fuel = queue.popleft()
        start = fuel
        if board[x][y] == 2: #도착한 경우
            if fuel >= 0:
                if start - fuel <= distance:
                    candidate.append([x, y, fuel])
                    distance = start - fuel

 

BFS 탐색은 이렇게 진행해주시고

for i in range(4):
    nx, ny = dx[i] + x, dy[i] + y
    if 0 <= nx < N and 0 <= ny < N:
        if not visited[nx][ny] and board[nx][ny] != 1 and 0 < fuel:
            visited[nx][ny] = True
            queue.append([nx, ny, fuel - 1])

 

탐색이 끝나면 후보가 있는지 확인 한 후

연료가 가장 많이 남고, 좌표가 작은 순으로 후보를 정렬 합니다.

이후 택시 좌표, 남은 연료, 도착 좌표를 return 합니다.

if candidate:
    candidate.sort(key=lambda x : (-x[2], x[0], x[1]))
    x, y, fuel= candidate[0]
    board[x][y] = 0
    M -= 1
    num = index_p[(x, y)]
    destx, desty = cord_d[num]
    return [x, y, fuel, destx, desty]

return [-1, -1, -1, -1, -1] #갈 곳이 없는 경우

 

다음은 도착지점으로 가는 함수 go_destination입니다. 

사용한 연료를 * 2를 해주어 남은 연료와 더해 연료를 업데이트 합니다.

def go_destination(x, y, fuel, destx, desty):
    queue = deque()
    origin = fuel
    queue.append([x, y, fuel])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True

    while queue:
        x, y, fuel = queue.popleft()
        if [x, y] == [destx, desty]:
            if fuel < 0:
                return -1
            return fuel + (origin - fuel) * 2

        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny] and board[nx][ny] != 1 and fuel > 0:
                    visited[nx][ny] = True
                    queue.append([nx, ny, fuel - 1])

    return -1

 

백준 19238 스타트 택시 Python 코드였습니다.

감사합니다.