[SWEA][Python3] 1798. 범준이의 제주도 여행 계획

나의 풀이 :

def dfs(rday, rmin, satis, last_visit):

found_points = False

for i, (m, s) in points.items():

if visited[i]:

continue

if rmin - m - distance[last_visit][i] >= 10:

found_points = True

path.append(i)

visited[i] = 1

dfs(rday, rmin - m - distance[last_visit][i], satis + s, i)

path.pop()

visited[i] = 0

if not found_points:

if rday > 1:

for i in hotels:

if distance[last_visit][i] <= rmin:

path.append(i)

dfs(rday-1, 540, satis, i)

path.pop()

else:

if rmin >= distance[last_visit][airport] and ans[0] < satis:

ans[0] = satis

ans[1] = path[1:] + [airport]

T = int(input())

for tc in range(1, T + 1):

N, M = map(int, input().split())

distance = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, N):

line = list(map(int, input().split()))

for j, d in enumerate(line, i+1):

distance[i][j] = distance[j][i] = d

hotels = []

points = {}

for i in range(1, N+1):

line = input()

if line[0] == 'P':

points[i] = list(map(int, line.split()[1:]))

elif line[0] == 'H':

hotels.append(i)

else:

airport = i

ans = [0, []]

visited = [0]*(N+1)

path = [airport]

dfs(M, 540, 0, airport)

print('#{} {} {}'.format(tc, ans[0], ' '.join(map(str, ans[1]))))

한마디 :

더 이상 방문할 관광포인트가 없을 때만 호텔이나 공항으로 간다는게 핵심이다.