BAEKJOON 19238 스타트 택시 Using Python

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

19238번: 스타트 택시

 

문제 설명.

문제는 핵심

1. 현재 택시 위치에서 연료내에 갈 수 있는 손님 중 가장 가까운 손님을 선택

2. 가장 가까운 손님이 겹칠 때, 행이 작은 손님 선택, 이것도 겹칠 때 열이 작은 손님을 선택

3. 연료내로 목적지 갈 수 있는지 판단하고 손님에서 목적지까지 가는 연료량을 다시 충전하기.

Edge Case

1. *edge 첫 택시 위치에 손님이 있을 수 있음

2. *edge 행과 열의 값을 위해서 정렬을 통해서 손님을 결정해야함

3. *edge 한 손님의 위치와 다른손님의 출발지가 겹칠 수 있다.

 

INPUT

input 값을 통해서 N이 최대 20이고 M이 400보다 작을 경우이니 반복 bfs를 이용할 수 있다고 생각했다.

OUTPUT

아래와 같이 손님이 이동못할 경우나, 연료가 바닥날 경우를 -1로 출력하고 다른 경우는 남은 연료 출력한다.

CODE

코드가 장황하게 길다. 코드에 대해서 주석을 다 달았기 때문에 주석을 읽어 본 후에 코드를 작성하면 할 수 있을 것이다.

# N이 20보다 작거나 같으므로 한번 다 탐색한다고 해도 400 번 탐색이니
# bfs를 써서 최단 거리를 찾는 것을 반복하면 시간 복잡도는 충분하다고 생각하고 구현했다.
from sys import stdin
delta = [[-1, 0], [0, -1], [0, 1], [1, 0]]

# 승객을 태울경우
def people_bfs(texi_E):
    global target
    # 방문 체크로 방문 했는지 안했는지 체크(bfs 방식)
    visited = [[0] * N for _ in range(N)]
    # 현재 위치와, 택시 에너지 넣기
    Q = [now + [texi_E]]
    # deque를 안쓰고 Q를 이용해 시간 복잡도를 줄이기 위해서
    front, rear = 0, 1
    # 이 값을 통해서 texi_e가 몇일 때 멈출수 있다.
    stop = 0
    # 여기에 값들을 넣어서 정열을 통해서 값을 비교하기
    answer = []
    # 현재 택시 에너지 값을 임의로 넣어줬다.
    now_texi_e = 0
    # bfs
    while front < rear:
        i, j, now_texi_e = Q[front]
        front += 1
        # 승객을 찾았던 택시에너지 보다 줄어 들었을 때 탐색을 종료, 이를 통해서 택시 에너지가 똑같을 때 찾은 승객들의 배열을 정렬 할 수 있다.
        if now_texi_e < stop:
            # 행, 열 순으로 정열
            answer.sort()
            # 위치 갱신
            now[0], now[1] = answer[0][0], answer[0][1]
            # 목적지 갱신
            target = answer[0][2]
            # 행열 갱신
            array[now[0]][now[1]] = 0
            # 에너지 반환(+1을 해주는 이유는 한번 더 간 texi_e를 현재 가지고 있기 때문이다.
            return now_texi_e + 1
        # array안에 리스트를 가지고 있는 경우(승객을 찾았다는 경우이다)
        if array[i][j]:
            # stop값을 지정해준다.
            stop = now_texi_e
            # 그리고 정답에 넣어준다.
            answer.append([i, j, array[i][j]])
        # 에너지가 0보다 작거나 같을 경우에는 더 이상 탐색 못하게 한다.
        if now_texi_e <= 0:
            continue
        # 탐색하기
        for x, y in delta:
            ni, nj = i + x, j + y
            # 범위 안에 있고, 방문을 안했을 경우
            if 0 <= ni < N and 0 <= nj < N and array[ni][nj] != 1 and not visited[ni][nj]:
                # 방문체크, Q에 append(위치, 에너지), rear값 +1
                visited[ni][nj] = 1
                Q.append([ni, nj, now_texi_e-1])
                rear += 1
    # 마지막으로 정렬을 위해서 한번 더 돌게 했는데 승객을 찾았던 것이 Q의 마지막일 수 있으므로 마지막으로 한번 더해준다.
    if answer:
        answer.sort()
        now[0], now[1] = answer[0][0], answer[0][1]
        target = answer[0][2]
        array[now[0]][now[1]] = 0
        return now_texi_e
    return -1
# 목적지 까지 갈 경우
def target_bfs(texi_E):
    global target
    visited = [[0] * N for _ in range(N)]
    visited[now[0]][now[1]] = 1
    Q = [now + [texi_E, 0]]
    front, rear = 0, 1
    while front < rear:
        i, j, now_texi_e, times = Q[front]
        front += 1
        # 목적지에 도착했을 경우
        if i == target[0] and j == target[1]:
            # 현재 위치 갱신
            now[0], now[1] = i, j
            # 연료 다시 넣기
            now_texi_e += times * 2
            # 연료 반환
            return now_texi_e
        # 택시가 더 이상 주행 못할 경우
        if now_texi_e < 1:
            continue
        # bfs
        for x, y in delta:
            ni, nj = i + x, j + y
            if 0 <= ni < N and 0 <= nj < N and array[ni][nj] != 1 and not visited[ni][nj]:
                visited[ni][nj] = 1
                Q.append([ni, nj, now_texi_e - 1, times+1])
                rear += 1
    return -1

N, M, E = map(int, stdin.readline().split())
array = [list(map(int, stdin.readline().split())) for _ in range(N)]
now = list(map(int, stdin.readline().split()))
now[0], now[1] = now[0] - 1, now[1] - 1
for i in range(M):
    si, sj, ei, ej = map(int, stdin.readline().split())
    # array 승객의 idx에 도착지 정보를 넣어준다. 이걸 통해서 승객의 출발지, 도착지가 겹치는 것을 방지한다.
    array[si-1][sj-1] = [ei - 1, ej - 1]
# config 0이면 손님 안탄것, config 1이면 손님 탄것
config, target = 0, [0, 0]
# 현재 연료량
now_E = E
# 승객수 파악
num = 0
# 승객을 다 도착 시켰을 경우 - 이 경우에는 num으로 파악
# 연로양이 바닥, 출발지과 목적지 이동X, 모든 손님을 이동 시킬수 없을 경우 - 이 경우에는 now_E로 나타낼 예정(now_E를 음수로 줄 예정)
while now_E > 0:
    if not config:
        now_E = people_bfs(now_E)
        config = 1
    else:
        now_E = target_bfs(now_E)
        num += 1
        config = 0
    if num == M:
        break
print(now_E)