스타트 택시

19238번: 스타트 택시

접근 방법 [필수 작성]

문제해석

손님 클리어시 연료 이동거리의 2배 충전

상하좌우 이동 가능

항상 최단경로만 이동 (BFS)

여러명 태우는 경우 없고, 한번에 한명만 가능

태울때는 가장 빨리 태울수 있는 사람 먼저 태움

같은 거리 승객이 여러명이면 더 작은 행번호 승객을 태움

연료바닥과 동시에 손님 배달 성공시 연료충전

연료바닥날시 업무종료

성공적으로 모든 손님 데려다 줄 수 있으면 남은 연료량 리턴

그게 아니면 -1 리턴

제한 조건 확인

아이디어

매트릭스 최대 크기 20x20

손님 최대명수 400명

연료 최대 50만

연료는 무한히 담을 수 있음

현재 택시위치에서 bfs 로 탐색하면서 cnt 를 1씩 늘려나감

bfs탐색중 만난 첫번째 손님을 태우면서 cnt 만큼 연료를 뺌( 만약 연료가 0 또는 음수가 되면 영업 종료 )

손님 태우고 목적지로 이동( 이때 손님이 2명일 경우 행수가 더 적은 손님을 태움)

목적지로 이동하면서 한칸당 cnt 1 증가 (목적지 도착시,

손님수 1명 줄이고,

cnt 만큼 연료빼고,

만약 연료가 음수면 영업종료

만약 연료가 0 또는 양수면 cnt*2 만큼 연료충전)

다시 bfs 탐색 반복 (벽때문에 데리러 갈 수 없는 손님이이나, 도착지까지 도착할 수 없는 경우도 있음)

두가지 bfs 탐색이 있을 수 있음

bfs를 하다가 처음 만난 손님이 있는 경우와

목표도착지까지의 거리를 계산하는 bfs 가 있을 수 있음

시간복잡도

보수적 접근

승객 1명당 bfs 연산수 최대 20x20

승객 최대 400명

승객당 이동 연산수 최대 20x20

따라서 400^3 = 6400만 → 시간 충분

자료구조

매트릭스 → 2중 리스트

승객 출발 도착 정보 → 딕셔너리

코드 구현 [필수 작성]

1차 시도 (2시간 소요)

한방에 통과!

→ 그러나.. 구현하는데 너무 시간이 오래걸렸다.. ㅠㅠ

from collections import deque
import sys

N,M,fuel = map(int,input().split()) #N은 매트릭스 크기, M은 승객수
matrix = []
matrix.append([1]*(N+1))
for _ in range(N):
    matrix.append([1]+list(map(int,input().split())))
# for list in matrix:
#     print(list)
r,c = map(int,input().split())
psg_start = [] #psg means passengers
psg_end = []
for _ in range(M):
    tmp = list(map(int,input().split()))
    psg_start.append(tuple(tmp[0:2]))
    psg_end.append(tuple(tmp[2:4]))

psg_start_set = set(psg_start)

dr = [1,0,-1,0]
dc = [0,1,0,-1]

flag = 0

tmp_visited = [[False]*(N+1) for _ in range(N+1)]

def is_valid(r,c,visited):
    global matrix
    
    if 1 <= r < N+1 and 1 <= c < N+1 and matrix[r][c] == 0 and visited[r][c] == False:
        return True
    return False
    
# print(N,M,fuel)
# for list in matrix:
#     print(list)
# print(r,c)
# print(psg_start)
# print(psg_end)

def find_next_psg(s_r,s_c): 
    #입력값: 시작위치, 출력값: 도착위치와 사용한 연료
    #만약 bfs 다 했는데 벽때문에 도착할 수 없으면
    #-1,-1,-1 출력
    global psg_start_set
    global tmp_visited
    
    result = []
    min_count = sys.maxsize
    q = deque([[s_r,s_c,0]])
    tmp_visited[s_r][s_c] = True
    
    while q:
        tr, tc, count = q.popleft() # t means tmp
        
        if min_count < count:
            continue
        
        if (tr,tc) in psg_start_set:
            result.append([tr,tc,count])
            min_count = count
            
        for i in range(4):
            nr = tr + dr[i]
            nc = tc + dc[i]
            if is_valid(nr,nc,tmp_visited):
                tmp_visited[nr][nc] = True
                count += 1
                q.append([nr,nc,count])
                count -= 1
    
    if len(result) == 0:
        return [-1,-1,-1]
    
    result.sort()
    
    psg_start_set.remove(tuple(result[0][0:2]))
    
    return result[0]

def go_to_destination(s_r,s_c,d_r,d_c):
    #출발지에서 도착지로 도착할 수 있으면 이동거리를 리턴
    #도착할 수 없으면 -1 리턴
    global tmp_visited
    
    q = deque([[s_r,s_c,0]])
    tmp_visited[s_r][s_c] = True
    while q:
        tr,tc,count = q.popleft()

        if (tr,tc) == (d_r,d_c):
            return count
        
        for i in range(4):
            nr = tr + dr[i]
            nc = tc + dc[i]
            if is_valid(nr,nc,tmp_visited):
                tmp_visited[nr][nc] = True
                count += 1
                q.append([nr,nc,count])
                count -= 1
    
    return -1

for i in range(M):
    #print(r,c,fuel)
    
    tmp_visited = [[False]*(N+1) for _ in range(N+1)]
    
    start_r, start_c, used_fuel = find_next_psg(r,c)
    
    if start_r == -1: # 막힌 벽때문에 손님을 태울 수 없는 경우
        #print("막힌 벽때문에 손님을 태울 수 없는 경우")
        flag = -1
        
    fuel -= used_fuel
    
    if fuel < 0: # 손님 태우러 가다가 연료 다 쓴 경우
        #print("손님 태우러 가다가 연료 다 쓴 경우")
        flag = -1
    
    if flag == -1:
        break
    
    #손님태우기 성공
    
    r = start_r
    c = start_c
    
    #print(r,c,fuel)
    
    tmp_visited = [[False]*(N+1) for _ in range(N+1)]
    
    d_r, d_c = psg_end[psg_start.index((start_r,start_c))]
    
    #print(d_r,d_c)
    
    used_fuel = go_to_destination(r,c,d_r,d_c)
    
    if used_fuel == -1: # 벽에 막혀 도착지에 도착할 수 없는 경우
        #print("벽에 막혀 도착지에 도착할 수 없는 경우")
        flag = -1
    
    if fuel - used_fuel < 0: # 손님 도착지 가다가 연료 오링난 경우
        #print("손님 도착지 가다가 연료 오링난 경우")
        flag = -1
        
    if flag == -1:
        break
    
    fuel += used_fuel # 도착지 도착 성공하면 이동거리의 2배 충전
    
    r = d_r
    c = d_c

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

배우게 된 점 [ 필수 X ]

set 의 원소는 immutable 해야한다.

list = [1,2,[3,4]]
a = set(list)
print(a)

a = set(list)
^^^^^^^^^
TypeError: unhashable type: 'list'

[ GPT 답변 ]

이 오류는 세트(set)에 추가하려는 원소가 변경 가능한(mutable) 자료형인 리스트입니다. 세트는 변경 불가능한(immutable) 자료형만 포함할 수 있습니다. 리스트는 값이 변경될 수 있는(mutable) 자료형이므로 세트에 직접 넣을 수 없습니다.

세트에 넣을 수 있는 원소는 불변(immutable)한 자료형이어야 합니다. 예를 들면 숫자, 문자열, 튜플 등이 해당됩니다. 리스트는 그 자체로 변경이 가능하기 때문에 세트에 포함될 수 없습니다.

원하는 결과를 얻기 위해서는 리스트 대신 튜플을 사용하면 됩니다. 튜플은 변경 불가능한 자료형이므로 세트에 추가할 수 있습니다.

질문 [ 필수 X ]

Q1

코드가 굉장히 길고 복잡한데 협업의 가독성 관점에서 개선할 부분이 있으면 말씀주시면 감사드리겠습니다.

특히 for 문의 반복되는 코드 부분을 더 개선할 수 있을것같은데 아이디어가 있으면 제시해주시면 감사드리겠습니다.

피드백 [ 코치 작성 ]

로직 자체는 간결하며 이해하기 편합니다. 특히 승객을 태우러 갈 때, 목적지로 갈 때를 구분해 작성한 점이 이후 반복문에서 함수를 사용함에 있어 가독성을 높였습니다. bfs함수만을 작성하여 두 기능을 모두 수행하고자 했다면 더욱 복잡해졌을 것입니다. 현재 가독성이 떨어진다고 느끼는 점은 개인적으로 너무 많은 개행 및 주석의 위치, 불필요한 출력문 주석 등이 원인으로 판단됩니다.

from collections import deque
import sys

#N은 매트릭스 크기, M은 승객수
N,M,fuel = map(int,input().split())

matrix = []
matrix.append([1]*(N+1))
for _ in range(N):
    matrix.append([1]+list(map(int,input().split())))

r,c = map(int,input().split())

psg_start = [] 
psg_end = []
for _ in range(M):
    tmp = list(map(int,input().split()))
    psg_start.append(tuple(tmp[0:2]))
    psg_end.append(tuple(tmp[2:4]))
psg_start_set = set(psg_start)

dr = [1,0,-1,0]
dc = [0,1,0,-1]
flag = 0
tmp_visited = [[False]*(N+1) for _ in range(N+1)]

def is_valid(r,c,visited):
    global matrix
    
    if 1 <= r < N+1 and 1 <= c < N+1 and matrix[r][c] == 0 and visited[r][c] == False:
        return True
    return False

# 다음 승객의 위치 찾기
def find_next_psg(s_r,s_c): 
    #입력값: 시작위치, 출력값: 도착위치와 사용한 연료
    #만약 bfs 다 했는데 벽때문에 도착할 수 없으면
    #-1,-1,-1 출력
    global psg_start_set
    global tmp_visited
    
    result = []
    min_count = sys.maxsize
    q = deque([[s_r,s_c,0]])
    tmp_visited[s_r][s_c] = True
    
    while q:
        tr, tc, count = q.popleft()
        
        if min_count < count:
            continue
        
        if (tr,tc) in psg_start_set:
            result.append([tr,tc,count])
            min_count = count
            
        for i in range(4):
            nr = tr + dr[i]
            nc = tc + dc[i]
            if is_valid(nr,nc,tmp_visited):
                tmp_visited[nr][nc] = True
                count += 1
                q.append([nr,nc,count])
                count -= 1
    
    if len(result) == 0:
        return [-1,-1,-1]
    
    result.sort()
    
    psg_start_set.remove(tuple(result[0][0:2]))
    
    return result[0]

def go_to_destination(s_r,s_c,d_r,d_c):
    #출발지에서 도착지로 도착할 수 있으면 이동거리를 리턴
    #도착할 수 없으면 -1 리턴
    global tmp_visited
    
    q = deque([[s_r,s_c,0]])
    tmp_visited[s_r][s_c] = True
    while q:
        tr,tc,count = q.popleft()

        if (tr,tc) == (d_r,d_c):
            return count
        
        for i in range(4):
            nr = tr + dr[i]
            nc = tc + dc[i]
            if is_valid(nr,nc,tmp_visited):
                tmp_visited[nr][nc] = True
                count += 1
                q.append([nr,nc,count])
                count -= 1
    
    return -1

for i in range(M):
    tmp_visited = [[False]*(N+1) for _ in range(N+1)]
    start_r, start_c, used_fuel = find_next_psg(r,c)
    
		# 막힌 벽때문에 손님을 태울 수 없는 경우
    if start_r == -1: 
        flag = -1
        
    fuel -= used_fuel    
		# 손님 태우러 가다가 연료 다 쓴 경우
    if fuel < 0: 
        flag = -1
    if flag == -1:
        break
    
    #손님태우기 성공
    
    tmp_visited = [[False]*(N+1) for _ in range(N+1)]
    r, c = start_r, start_c
    d_r, d_c = psg_end[psg_start.index((start_r,start_c))]
    used_fuel = go_to_destination(r,c,d_r,d_c)
    
		# 벽에 막혀 도착지에 도착할 수 없는 경우
    if used_fuel == -1: 
        flag = -1
    
		# 손님 도착지 가다가 연료 오링난 경우
    if fuel - used_fuel < 0: 
        flag = -1
    if flag == -1:
        break
    
    fuel += used_fuel # 도착지 도착 성공하면 이동거리의 2배 충전
    r, c = d_r, d_c

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

또한 협업의 측면에서 보면 변수명이 다소 직관적이지 않은 점이 있으며 이는 파이썬 스타일 가이드(구글 등)를 통해 확인할 수 있습니다.

코드 로직의 측면에서는 flag를 처리하는 if문을 통합해 간결하게 줄일 수 있으며 visited는 매 함수 호출마다 초기화해야 하는 변수이기에 함수 내부에서 선언하는 것이 좋습니다.