[백준][구현] 스타트 택시

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

19238번: 스타트 택시

 

내가 작성한 코드

from collections import defaultdict, deque

dir = [(-1,0),(0,-1),(0,1),(1,0)]

def in_range(r, c, N):
    return 0<=r<N and 0<=c<N

def read_data():
    N, M, F = map(int, input().rstrip().split())
    board = []
    passenger = defaultdict(tuple)
    for _ in range(N):
        board.append(list(map(int, input().rstrip().split())))
    r, c = map(lambda x: x-1, map(int, input().rstrip().split()))
    for _ in range(M):
        src_r, src_c, dest_r, dest_c = map(int, input().rstrip().split())
        passenger[(src_r-1, src_c-1)] = (dest_r-1, dest_c-1)
    return N, M, F, board, passenger, r, c

def get_distance(r, c, dest_r, dest_c, mn, cand, board, F):
    visited = defaultdict(bool)
    q = deque([(r, c, 0)])
    visited[(r, c)] = True

    while q:
        i, j, crnt = q.popleft()

        if i == dest_r and j == dest_c:
            if crnt < mn:
                mn = crnt
                cand = (r, c)
            elif (i, j) < cand:
                cand = (r, c)
            return mn, cand

        for d_r, d_c in dir:
            nw_r, nw_c = i+d_r, j+d_c
            if in_range(nw_r, nw_c, N) and not visited[(nw_r, nw_c)] and\
                    crnt+1 <= mn and crnt+1 <= F and board[nw_r][nw_c] != 1:
                visited[(nw_r, nw_c)] = True
                q.append((nw_r, nw_c, crnt+1))
    return mn, cand

def choose_passenger(N, F, board, passenger, r, c):
    mn = float('inf')
    cand = (N, N)

    visited = defaultdict(bool)
    q = deque([(r, c, 0)])
    visited[(r, c)] = True

    while q:
        i, j, crnt = q.popleft()

        if passenger[(i, j)]:
            if crnt < mn or (crnt==mn and (i, j) < cand):
                mn = crnt
                cand = (i, j)
            continue

        for d_r, d_c in dir:
            nw_r, nw_c = i + d_r, j + d_c
            if in_range(nw_r, nw_c, N) and not visited[(nw_r, nw_c)] and\
                    crnt+1 <= mn and crnt+1 <= F and board[nw_r][nw_c] != 1:
                visited[(nw_r, nw_c)] = True
                q.append((nw_r, nw_c, crnt+1))

    # print(f"{F}\t {mn}\t {cand}")
    return mn, cand

def take_passenger(N, F, board, passenger, cand):
    mn = float('inf')
    nw_cand = (N, N)
    mn, nw_cand = get_distance(cand[0], cand[1], passenger[cand][0], passenger[cand][1], mn, nw_cand, board, F)
    # print(f"{F}\t {mn}\t {passenger[cand]}")
    return mn, passenger[cand]

def get_answer(N, M, F, board, passenger, r, c):
    for _ in range(M):
        f, cand = choose_passenger(N, F, board, passenger, r, c)
        if f == float('inf'):
            return -1
        F -= f
        f, taxi = take_passenger(N, F, board, passenger, cand)
        if f == float('inf'):
            return -1
        F += f
        del passenger[cand]
        r, c = taxi
    return F

def test():
    # N, M, F = 6, 3, 15
    # board = [[0, 0, 1, 0, 0, 0],
    #         [0, 0, 1, 0, 0, 0],
    #         [0, 0, 0, 0, 0, 0],
    #         [0, 0, 0, 0, 0, 0],
    #         [0, 0, 0, 0, 1, 0],
    #         [0, 0, 0, 1, 0, 0]]
    # r, c = 6, 5
    # r -= 1
    # c -= 1
    # passenger = defaultdict(tuple)
    # tmp = [ (2, 2, 5, 6),
    #         (5, 4, 1, 6),
    #         (4, 2, 3, 5)]
    # for _a, _b, _c, _d in tmp:
    #     passenger[(_a-1, _b-1)] = (_c-1, _d-1)

    N, M, F = 20, 19 * 19, 500000
    board = [[0 for _ in range(N)] for _ in range(N)]
    r, c = 1, 1
    r -= 1
    c -= 1
    passenger = defaultdict(tuple)
    tmp = [(i, j, i+1, j+1) for i in range(19) for j in range(19)]
    for _a, _b, _c, _d in tmp:
        passenger[(_a-1, _b-1)] = (_c-1, _d-1)
    return N, M, F, board, passenger, r, c

N, M, F, board, passenger, r, c = read_data()
# N, M, F, board, passenger, r, c = test()
print(get_answer(N, M, F, board, passenger, r, c))

• 주먹구구식 코드
  • 코드 중복을 줄이려다가 + 알고리즘을 수정하려다가 매우 지저분한 코드가 됨...
• 승객 선택
  
  • 현재 택시 위치에서 BFS
  • queue에 push하는 조건들
    • 격자 범위
    • 방문 x
    • 현재 거리 <= 거리 최소값
    • 현재 거리 <= 연료
    • 벽 x
  • 탐색 중인 위치가 승객이 있는 위치이면 (dictionary)
    • 현재 거리 < 최소값 or (현재 거리 == 최소값 and 현재 위치 < 최소 위치)
    • 최소값 / 최소 위치 업데이트
• 승객 데려다주기
  • 위 queue에 push하는 조건들을 포함하여 탐색
  • 조건을 만족하지 않을 경우 -1

 

다른 사람이 작성한 코드

None

• 강한 구현문제로 다른 코드를 참고하지 않음

 

기억해야할 것

• 함수 체계화 필요
  • 함수를 더 세분화할 필요성을 느낌
  • 중간에 알고리즘이 바뀌면 바꿀 코드가 많아 시간이 걸림