[백준] 19238 스타트 택시 Python (구현/삼성기출)

Algorithm (PS)

[백준] 19238 스타트 택시 Python (구현/삼성기출)

minjiwoo 2023. 9. 10. 15:22

728x90

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

19238번: 스타트 택시

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다

www.acmicpc.net

시도 1 : 실패 -> TC2번과 3번에서 걸리고 있음

from collections import deque
N, M, fuel = map(int, input().split()) # fuel = 15
board = []
flag = True

customer = []
for _ in range(N):
    board.append(list(map(int, input().split())))
sx, sy = map(int, input().split()) # taxi start position
sx -= 1 # board 랑 index 맞추기
sy -= 1

for _ in range(M):
    ax, ay, bx, by = map(int, input().split())
    customer.append([ax-1, ay-1, bx-1, by-1])
customer.sort() # 행, 열 순으로 정렬

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

# 1. 거리가 가장 가까운 손님 구하기
def next_customer():
    global fuel, sx, sy
    distance = [[-1] * N for _ in range(N)] # taxi 좌표에서 모든 칸까지의 거리를 저장
    queue = deque([])
    queue.append((sx, sy))
#    distance[sx][sy] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))
    min_dist = int(1e9)
    next_cus = [0, 0, 0, 0] # next customer 좌표
    # check customer
    for c in customer:
        ax, ay, bx, by = c[0], c[1], c[2], c[3] # 출발지 좌표만 사용
        if min_dist > distance[ax][ay]:
            min_dist = distance[ax][ay]
            next_cus = [ax, ay, bx, by]
    # Fuel Check
    if fuel < min_dist:
        flag = False
        print(-1)
        exit(1)
    else:
        fuel -= min_dist
        sx, sy = next_cus[0], next_cus[1]

    return next_cus

# 2. 손님을 출발지에서 목적지로 이동시키기
def move(ax, ay, bx, by):
    # 목적지에서 출발지까지의 거리 구하기
    distance = [[-1] * N for _ in range(N)]
    queue = deque([])
    queue.append((ax, ay))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))
    return distance[bx][by] # dist



while len(customer):
    c = next_customer()
    # 삭제하기 ?
    customer.remove(c)
    customer.sort()
    dist = move(c[0], c[1], c[2], c[3])
    if fuel > dist: # 손님 이동시키기 성공 한 경우
        fuel += dist
        sx, sy = c[2], c[3] # 손님의 목적지가 택시의 새로운 출발지점이 된다.
    else:
        flag = False
        break

if flag:
    print(fuel)
else:
    print(-1)

시도2 : 테케 1, 2는 맞췄으나 여전히 테케 3에서 걸린다.

from collections import deque
N, M, fuel = map(int, input().split()) # fuel = 15
board = []
flag = True

customer = []
for _ in range(N):
    board.append(list(map(int, input().split())))
sx, sy = map(int, input().split()) # taxi start position
sx -= 1 # board 랑 index 맞추기
sy -= 1

for _ in range(M):
    ax, ay, bx, by = map(int, input().split())
    customer.append([ax-1, ay-1, bx-1, by-1])
customer.sort() # 행, 열 순으로 정렬

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

# 1. 거리가 가장 가까운 손님 구하기
def next_customer():
    global fuel, sx, sy
    distance = [[-1] * N for _ in range(N)] # taxi 좌표에서 모든 칸까지의 거리를 저장
    queue = deque([])
    queue.append((sx, sy))
    distance[sx][sy] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))
    min_dist = int(1e9)
    next_cus = [0, 0, 0, 0] # next customer 좌표
    # check customer
    for c in customer:
        ax, ay, bx, by = c[0], c[1], c[2], c[3] # 출발지 좌표만 사용
        if min_dist > distance[ax][ay]:
            min_dist = distance[ax][ay]
            next_cus = [ax, ay, bx, by]
    # Fuel Check
    if fuel < min_dist:
        flag = False
        print(-1)
        exit(1)
    else:
        fuel -= min_dist
        sx, sy = next_cus[0], next_cus[1]

    return next_cus

# 2. 손님을 출발지에서 목적지로 이동시키기
def move(ax, ay, bx, by):
    # 목적지에서 출발지까지의 거리 구하기
    distance = [[-1] * N for _ in range(N)]
    distance[ax][ay] = 0
    queue = deque([])
    queue.append((ax, ay))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))
    return distance[bx][by] # dist



while customer:
    c = next_customer()

    customer.sort()
    dist = move(c[0], c[1], c[2], c[3])
    if fuel > dist: # 손님 이동시키기 성공 한 경우
        fuel += dist
        sx, sy = c[2], c[3] # 손님의 목적지가 택시의 새로운 출발지점이 된다.
    else:
        flag = False
        print(-1)
        exit()
        break
    # 삭제하기 ?
    customer.remove(c)

if flag:
    print(fuel)
else:
    print(-1)

정답코드

1. 예제 3과 같은, 택시가 아예 승객을 못태울 수도 있는 경우에 대해 예외처리를 했다.

2. 문제 본문에서 '승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.' 라고 하였는데 .. 이를 반영하기 위해서 등호를 추가했다. 역시 문제를 잘읽자..!

if fuel >= dist: # 손님 이동시키기 성공 한 경우
    fuel += dist
    sx, sy = c[2], c[3] # 손님의 목적지가 택시의 새로운 출발지점이 된다.

from collections import deque
N, M, fuel = map(int, input().split()) # fuel = 15
board = []
flag = True

customer = []
for _ in range(N):
    board.append(list(map(int, input().split())))
sx, sy = map(int, input().split()) # taxi start position
sx -= 1 # board 랑 index 맞추기
sy -= 1

for _ in range(M):
    ax, ay, bx, by = map(int, input().split())
    customer.append([ax-1, ay-1, bx-1, by-1])
customer.sort() # 행, 열 순으로 정렬

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

# 1. 거리가 가장 가까운 손님 구하기
def next_customer():
    global fuel, sx, sy, flag
    distance = [[-1] * N for _ in range(N)] # taxi 좌표에서 모든 칸까지의 거리를 저장
    queue = deque([])
    queue.append((sx, sy))
    distance[sx][sy] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))

    min_dist = int(1e9)
    next_cus = [0, 0, 0, 0] # next customer 좌표
    # check customer
    for c in customer:
        ax, ay, bx, by = c[0], c[1], c[2], c[3] # 출발지 좌표만 사용
        if min_dist > distance[ax][ay]:
            min_dist = distance[ax][ay]
            next_cus = [ax, ay, bx, by]
    if min_dist == -1 or min_dist == int(1e9):
        print(-1)
        exit()
    # Fuel Check
    if fuel < min_dist:
        flag = False
        print(-1)
        exit()
    else:
        fuel -= min_dist
        sx, sy = next_cus[0], next_cus[1]

    return next_cus

# 2. 손님을 출발지에서 목적지로 이동시키기
def move(ax, ay, bx, by):
    # 목적지에서 출발지까지의 거리 구하기
    distance = [[-1] * N for _ in range(N)]
    distance[ax][ay] = 0
    queue = deque([])
    queue.append((ax, ay))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))
    return distance[bx][by] # dist



while customer:
    c = next_customer()
    dist = move(c[0], c[1], c[2], c[3])
    if fuel >= dist: # 손님 이동시키기 성공 한 경우
        fuel += dist
        sx, sy = c[2], c[3] # 손님의 목적지가 택시의 새로운 출발지점이 된다.
    else:
        flag = False
        print(-1)
        exit()
        break
    # 삭제하기
    customer.remove(c)
    customer.sort()

if flag:
    print(fuel)
else:
    print(-1)

728x90