| 시간 제한 | 메모리 제한 |
| 10초 / 3 | 128MB / 128MB |
문제
https://www.acmicpc.net/problem/2782
로맨틱왕: 최대 16개의 선물나무를 선택하거나, 선택하지 않을 수 있으며 선물나무를 선택할 때마다 왕이 1칸을 이동하는데 소모되는 시간이 1씩 증가한다. 왕은 처음에 1칸 당 1시간의 속도로 이동할 수 있다. 왕이 왕비가 있는 곳까지 제한 시간 내에 가져갈 수 있는 최대 선물의 수를 구하는 문제. 선물나무의 위치에 도착했다고 반드시 선물을 가져가는 건 아니고 선물나무마다 선물을 1개 까지 가져갈 수 있다.
https://www.acmicpc.net/problem/8138
Tourist Attractions: 1~n까지의 지점을 두고 연결 그래프의 형태로 그려진 관광지에서 1에서 출발해 2 ~ k + 1까지의 지점을 반드시 방문하고 n지점으로 도착하는 최단 경로의 총 길이를 구하는 문제. 한 지점을 여러 번 방문해도 상관 없고, 지점 간의 지켜야 하는 선후 관계가 있다.
입력
로맨틱 왕: 왕은 K, 왕비는 Q, 선물나무는 G, 지날 수 있는 곳은 ., 지날 수 없는 곳은 #으로 표시되어 가로, 세로 각각 최대 50칸의 그리드로 전체 필드가 주어진다. 반드시 왕이 왕비에게 갈 수 있는 경우만 주어지며 입력에서 왕이 도착할 수 없는 선물나무가 주어질 수도 있다.
Tourist Attractions: 지역 번호가 1부터 n까지로 주어지며 연결 관계와 가중치가 주어진다. 그래프는 양방향 그래프다.
출력
로맨틱 왕: 제한 시간 내에 왕이 왕비에게 가져갈 수 있는 최대 선물의 수
Tourist Attractions: 1에서 출발해 2 ~ k + 1의 모든 지점을 지나 n으로 도착하는 최단 경로의 길이
풀이
먼저 로맨틱 왕 부터 좀 볼까요.
시간 초과 잡는데 5일, 반례 잡는데 2주 썼습니다.
1. 로맨틱 왕
1) 접근, 단순 TSP의 실패 원인
처음에는 단순하게 생각했습니다. 그리드 상에서 BFS를 쭉 돌리며 각 지점과 지점 사이의 거리부터 확인해야 했어요. 모든 지점에 번호를 매기고, 그걸 그래프로 변환했습니다. 정점의 수가 왕, 왕비까지 다해서 최대 18개 밖에 되지 않기 때문에 각 지점 사이의 최단 거리는 플로이드-워셜 알고리즘으로 구할 수 있었습니다. 여기까진 별 문제가 되지 않았어요.
dp 테이블은 이전에 풀던 문제들과 동일하게 dp[now][visit] = now에서 출발해 visit의 비어있는 비트를 모두 방문하는 최단 경로로 정의했습니다.
TSP를 돌려서 왕으로부터 왕비까지 갈 수 있는 거리를 생각해보니 선물을 하나도 들고 가지 않아야 거리만으로 풀 수 있더라고요? 선물을 하나 들게 되면 그 때부터는 모든 이동에 시간이 1씩 더 걸립니다. 가장 먼저 생각한 방법은 모든 선물 나무를 모조리 방문하는 거였어요. 그러면 visit에서 켜져있는 비트의 수를 다음 탐색 지점까지 거리에 곱해버리면 다음 가중치가 되거든요.
그래서 이렇게 코드를 짜봤더니 결과가 이상하게 나왔습니다. 이유는 왕이 제한 시간 내에 왕비에게 도착할 수 없는 경우가 있었어요. 그 이유는 이 탐색 방법은 모든 선물 나무 방문을 강제하기 때문입니다. 문제 조건에 따르면 일부 선물 나무에서 선물을 가져가지 않는 방법도 있습니다.
비트필드를 활용한 다이나믹프로그래밍으로 최적화된 TSP에서는 위 그림과 같이 K-1-2-3-4-Q의 탐색을 하는 과정에서 3-4-Q의 탐색을 하위 탐색으로 저장할 거예요. 이걸 나중에 꺼내서 K와 이어붙여버리면 K-3-4-Q라는 새로운 탐색을 만들 수 있습니다. 그러니까 1, 2를 제외한 탐색도 꺼내올 수 있습니다. 그런데 여기 이런 문제가 있었습니다.
K에서 3으로 직행하는 거리는 3이라고 쳐봅시다. 그럼 이건 그대로 거리 정보를 가져올 수 있습니다. 왜냐면 처음엔 왕의 이동 속도가 1칸에 1시간이기 때문입니다. 그런데 이전에 탐색했던 정보를 그대로 가져오면 3번 나무를 지나 4번 나무를 갈 때 왕이 선물을 이미 3개나 들고 있는 상태의 정보가 넘어옵니다. Q에게 갈 때는 선물이 4개입니다. 실제로 탐색한 전체 선물은 2개인데 말입니다. 따라서 이렇게 실제 K에서 Q까지의 탐색 중 하위 탐색들의 소모 시간을 그대로 저장했다간 선물 갯수가 맞지 않아 잘못된 정보를 가져오게 됩니다. 이걸 해결할 방법으로 두 가지를 떠올렸습니다.
2) 3차원 DP와 경로 길이DP
먼저 시도했던 방법입니다. 처음에 했던 dp테이블의 정의를 고쳤습니다. 선물 갯수 정보를 함께 관리할 수 있도록 했어요.
이제 dp[now][gift][visit] = now에서 gift개의 선물을 가지고 visit의 비어있는 비트를 모두 방문하는 최단 경로 입니다. 이러면 선물이 최대 16개니까 왕에서 출발해 16개의 선물까지 나타낼 17개의 비트필드가 217개 만큼 필요하고 그 비트필드가 17개 정점에서 0~16개 까지의 선물, 즉 선물의 17가지 상태 만큼 필요합니다. 대충 217*17*17*4B(int) = 151,519,232B ≒ 152MB가 dp테이블 관리에만 투자됩니다. 메모리 초과예요.
두 번째 시도는 새로운 DP테이블을 추가하는 것이었습니다. 이 방법은 방금 전 3차원 만큼의 공간은 필요하지 않았습니다.
아이디어는 이런 식입니다. K에서 탐색을 시작, 하위탐색으로 넘어갑니다. 1에서도, 2에서도, 3에서도 하위탐색으로 넘어갑니다. 이제 그림상에 가장 아래에 있는 4에서 탐색을 시작합니다. 이미 상위에서 K, 1, 2, 3의 비트가 채워져있는 채로 넘어왔기 때문에 탐색해야 할 dp테이블이 위치는 dp[4][11111]입니다. 모든 비트가 가득 찼기 때문에 곧바로 테이블의 값을 상위 탐색으로 넘깁니다. 이때 4에서 Q로 가는 최단 경로인 4를 dist[4][11111]에 함께 저장하고 반환해줍니다. 그 위에서는 하위 탐색의 결과로 dp 값을 갱신하고 갱신될 때 하위 탐색에서 얻은 dist를 더해서 관리합니다. 위 그림 상에서는 9입니다. 이게 무슨 의미냐면 왕이 3에서 출발해 4를 지나 Q로 간다면 시간이 9가 걸립니다. 하지만 K는 3에서 출발하지 않습니다. 여기서 K-3-4-Q의 dist 값을 더해주면 K가 3과 4를 지나 Q로 가는 시간이 완성됩니다. 이 방법을 통해 왕이 선물을 갖고 왕비에게 가는 시간을 누적합으로 구할 수 있습니다.(라고 생각했습니다.)
def TSP(now, visit, depth):
if tsp_dp[now][visit] == inf:
bit = 1
for i in range(1, gift_count):
bit <<= 1
if visit & bit: continue
# k는 하위 탐색에서 반환된 소모 시간
k = TSP(i, visit | bit, depth + 1)
new_dist = link[now][i] + dist[i][visit | bit]
k += new_dist
# new_dist가 더해진 k는 현재 위치에서 예상되는 소모 시간
# k가 현재 저장된 값보다 작은 경우
# tsp_dp와 dist를 모두 갱신
# k는 같은데 dist가 더 짧아질 수 있는 경우
# dist만 갱신
if k + (new_dist * depth) < tsp_dp[now][visit] + (dist[now][visit] * depth):
tsp_dp[now][visit] = k
dist[now][visit] = new_dist
elif k == tsp_dp[now][visit] and dist[now][visit] > new_dist:
dist[now][visit] = new_dist
'''
# tsp_dp 갱신 조건 변경
if k + new_dist < tsp_dp[now][visit] + dist[now][visit]:
tsp_dp[now][visit] = k
dist[now][visit] = new_dist
'''
return tsp_dp[now][visit]3) 반례 찾기
거리 누적합 dp 관리로 주어진 예시입력과 게시판에 올라온 모든 반례가 다 통과 됐습니다. 그런데도 채점은 25%를 넘기질 못했고... 뭔가 찾지 못하는 반례가 있는 것 같아서 이런 저런 시도를 하다가 챗gpt에게 반례찾아달라 했더니 이런 반례를 줬습니다.
1
3 3 27
G#G
.Q#
G.K
res: 1
ans: 2뭐가 문제였냐면, 도달할 수 없는 선물 나무의 정보가 그래프와 dp 테이블에 남아있었던 거예요. 그래서 초기 그래프 구성 단계에서 왕이 갈 수 없는 선물 나무는 아예 정점으로 관리하지 않기로 했습니다. 그렇게 개선했는데도 채점 결과는 25%를 못넘겼습니다.
랜덤하게 반례를 생성하는 코드를 짜서 브루트포스로 확실한 정답을 구하고, 제가 짠 TSP 코드로 얻은 최적해를 비교해보도록 했습니다.
def solution1():
return # 거리 누적합 tsp
def solution2():
return # 브루트포스 tsp
case_count = 1
while True:
h, w, limit = random.randint(1, 50), random.randint(1, 50), 0
gifts = random.randint(5, 8)
city = [['.'] * w for _ in range(h)]
kx, ky = random.randint(0, h - 1), random.randint(0, w - 1)
city[kx][ky] = 'K'
while True:
x, y = random.randint(0, h - 1), random.randint(0, w - 1)
if city[x][y] == '.':
city[x][y] = 'Q'
limit = random.randint((abs(kx - x) + abs(ky - y)), 1000)
break
for _ in range(gifts):
while True:
x, y = random.randint(0, h - 1), random.randint(0, w - 1)
if city[x][y] == '.':
city[x][y] = 'G'
break
TSP = solution1(h, w, limit, city)
BF = solution2(h, w, limit, city)
if TSP != BF:
print('edge case exist')
print(f'{h} {w} {limit}')
for line in city:
print(*line, sep='')
break
else:
print(f'case {case_count} finished, TSP:{TSP}, BF:{BF}')
case_count += 1직접 탐색 과정을 살펴볼 수 있어야 하기 때문에 선물 나무 수는 좀 작게 설정했습니다. 이걸 돌려본 결과, 몇 개의 반례를 찾을 수 있었어요.
2
10 34 296
.Q................................
........G.........................
...........G......................
.........K........................
..................................
..................................
........G.................G.......
.....G............................
......G.G.........................
.................................G
23 32 291
....................Q...........
...............................G
................................
................................
G...............................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
......................G.........
................................
................................
................................
.........K......................
................................
................................
.........................G......
res
7
3
ans
8
4원인은 누적합으로 관리된 dp 값을 기준으로 최적해를 상위 탐색으로 반환하는 과정에 있었습니다. 하위 탐색이 가장 짧더라도 상위 탐색에서 다른 경로에 밀려나는 경우가 있습니다. 따라서 가장 짧은 경로만 반환하는 그리디(?)한 dp로는 최적해 구성이 안되더라구요. 그래서 처음부터 다시 생각했습니다.
정점 간 거리가 이렇게 주어진 그래프가 있다고 쳐봅시다. 제한 시간은 291입니다. 여기서 K-2-4-3-1-Q의 탐색을 살펴보면 이런 결과가 나옵니다.
dist 값이 작은 쪽으로 갱신하다보면 이게 4개의 선물을 들고 가는 최적해입니다. 그런데 총 시간이 제한을 넘겼기 때문에 4개를 들고가는 방법은 없다는 탐색 결과를 내놓습니다. 그런데 이런 탐색이 가능합니다.
2-3-4-1-Q로 이어지는 탐색은 dp값이 182로 2-4-3-1-Q로 이어지는 탐색보다 걸리는 시간이 더 큽니다. 그런데 K까지 붙어버리면 이 경우는 시간 제한 내에 선물 4개 들고 도착이 가능합니다. 이런 방식으로는 최적해를 구하기가 어려워보입니다.
4) 거꾸로 탐색하기
지금 문제는 왕에서 선물을 들고 갈 때마다 소모 시간이 길어진다는 거예요. 그런데 왕이 도착할 때 선물을 몇 개 들고 있을 수 있는지 알 수가 없다는 점이 제일 큰 문제입니다. 나중에 dp테이블의 값을 재활용하려고 해도 갖고 있는 선물의 수가 다르다면 쓸모가 없어져요. 남은 경로의 거리 정보를 활용해도 최적해를 구성하는 건 답이 아니었습니다.
그럼 반대로 가면 어떨까요? 왕비에서 출발해 왕까지 가는 방법을 찾는 것도 어차피 경로가 구성된다면 답은 같을 겁니다. 선물 나무에 방문 할 때마다 속도가 빨라진다는 점이 왕과는 반대입니다. 왕은 왕비에게 가까운 탐색을 시도했을 때 선물의 갯수를 특정할 수 없다는 것이 문제였습니다. dp[3][01011]로 탐색한 결과가 선물을 앞으로 3개만 들고 간다는 건지, 4개를 들고 간다는 건지 알 수가 없기 때문에 이 값이 어떤 시간을 가져야 하는지 특정이 안됩니다. 하지만 반대로 탐색한다면 다릅니다.
왕에게 가기 직전의 탐색은 반드시 선물이 없는 상태여야 합니다. 비트가 1개 비어있는 채로 왕에게 가는 탐색은 반드시 선물을 1개 들고 있다가 방문할 선물 나무에서 선물을 두고 가는 탐색이어야 합니다. 이제 소모 시간이 확정됩니다.
Q-4-3-2-1-K로 탐색하는 과정에서 2-1-K를 탐색하게 됩니다. 이 값은 선물의 양이 확정적이기 때문에 저장해두면 나중에 다른 처리 없이 바로 재활용이 가능합니다.
2. Tourist Attractions
1) 접근, 모든 것에는 다 이유가 있다.
지점 갯수는 20개, 주어지는 조건에 맞춰 먼저 탐색해야 하는 비트들이 채워져있는 경우에만 TSP를 돌려주면 답이 금방 나올 것 같습니다. 심지어 이거랑 같은 문제(백준 30975 약간 모자라지만 착한 친구야)를 풀어봤어요. 하지만 그 문제와 다른 점이 있다면 메모리 제한이 4배입니다.
지점이 20개, 출발과 도착까지 합치면 20개의 지점을 놓고 그래프가 그려집니다. 여기서 TSP를 돌리면 22개의 비트를 표현하는 비트필드 dp테이블이 필요합니다. 222*22*4B(int) = 369,098,752B ≒ 369MB. 메모리 한참 초과네요. 마지막 도착지점은 비트에서 빼줄 수 있으니까 빼보면 185MB. 그래도 안되네요. 뭐 어떡하지?
2) 비트필드는 비트 하나 추가할 때마다 메모리가 2배
비트필드는 당연히 비트니까 관리해야 할 지점이 하나 늘면 메모리가 2배입니다. 이게 수가 적으면 상관 없는데 한 20개쯤 부터는 늘어나는 메모리의 단위가 MB로 바뀌어서 문제가 됩니다. 24쯤 되면 더 이상은 비트필드로 관리 불가입니다. 그러니까 최대한 비트가 늘어나지 않는 쪽으로 생각하는 게 좋겠습니다.
이 문제에서는 출발 지점도 빼보기로 했어요. 그럼 딱 20개 지점만 보면 됩니다. 그러면 메모리가 대충 92MB쯤 나옵니다. 이제야 약간 가능성이 있는 수준이에요. 출발지점을 비트에서 빼버리면 모든 지점에서 출발을 한 번씩 해봐야 합니다. 이건 for문으로 구현 쉽게 할 수 있으니까 그렇게 합니다.
3) 허무한 예외 관리
엇 그런데 문제에서는 반드시 순회가 가능한 경우만 주어진댔는데 아닌 것 같은 경우가 있습니다. 마지막에 result 값을 매우 큰 값으로 해놓고 TSP를 돌려서 작은 값으로 갱신되도록 합니다. 그런데 결과가 매우 큰 값 그대로 나오는 경우가 있었습니다.
방문해야하는 지점이 없는 경우...는 탐색이 아예 없습니다. 이 때는 출발지점에서 도착지점으로 직행하는 최단 경로를 반환합니다.
(이거 찾는데도 시간 꽤 걸렸음..)
정답 코드
# 2782: 로맨틱 왕
import sys
from collections import deque
input = sys.stdin.readline
inf = 1000000
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
t = int(input())
def TSP(now, visit, depth):
if dp[now][visit] == inf:
bit = 1
for next in range(1, gift_count):
bit <<= 1
if visit & bit: continue
k = TSP(next, visit | 1 << next, depth - 1) + dist[now][next] * depth
o = dp[now][visit]
dp[now][visit] = min(o, k)
return dp[now][visit]
for _ in range(t):
h, w, limit = map(int, input().split())
city = [list(input().strip()) for _ in range(h)]
# 좌표 확인
gift = deque()
gift_cor = dict()
gift_count = 1
kx, ky = 0, 0
qx, qy = 0, 0
check_queen = [[0] * w for _ in range(h)]
for i in range(h):
for j in range(w):
if city[i][j] == 'Q':
qx, qy = i, j
gift_cor[(i, j)] = 0
bfs_queen = deque([(i, j)])
check_queen[i][j] = 1
while bfs_queen:
x, y = bfs_queen.popleft()
for k in range(4):
dx, dy = x + d[k][0], y + d[k][1]
if 0 <= dx < h and 0 <= dy < w and check_queen[dx][dy] == 0 and city[dx][dy] != '#':
bfs_queen.append((dx, dy))
check_queen[dx][dy] = 1
elif city[i][j] == 'K':
kx, ky = i, j
elif city[i][j] == 'G':
gift.append((i, j))
gift_count += 1
# K에서 닿지 않는 G는 그래프에서 제외
real_gift_count = 1
not_gift_count = 0
gift.append((qx, qy))
for i in range(gift_count - 1):
gx, gy = gift.popleft()
if check_queen[gx][gy]:
gift_cor[(gx, gy)] = real_gift_count
gift.append((gx, gy))
real_gift_count += 1
else:
not_gift_count += 1
gift_count -= not_gift_count
gift.append((kx, ky))
gift_cor[(kx, ky)] = gift_count
dist = [[inf] * (gift_count + 1) for _ in range(gift_count + 1)]
# 거리 확인
bfs = deque()
for i in range(gift_count):
check = [[0] * w for _ in range(h)]
bfs.append((gift[i]))
check[bfs[0][0]][bfs[0][1]] = 1
distance = 0
while bfs:
distance += 1
roop_count = len(bfs)
for _ in range(roop_count):
x, y = bfs.popleft()
for k in range(4):
dx, dy = x + d[k][0], y + d[k][1]
if 0 <= dx < h and 0 <= dy < w and city[dx][dy] != '#' and check[dx][dy] == 0:
check[dx][dy] = 1
if city[dx][dy] != '.':
j = gift_cor[(dx, dy)]
dist[i][j] = distance
dist[j][i] = distance
bfs.append((dx, dy))
dp = [[inf] * (1 << gift_count) for _ in range(gift_count + 1)]
# K에서 출발하는 경로 설정
k = (1 << gift_count) - 1
for i in range(gift_count):
dp[i][k] = dist[i][gift_count]
TSP(0, 1, gift_count)
# Q로 도착하는 최적해 확인
res = 0
for i in range(1, 1 << gift_count, 2):
if dp[0][i] <= limit:
count = 0
bit = 1
for k in range(1, gift_count):
bit <<= 1
if not(i & bit): count += 1
if res < count:
res = count
# G에서 출발하는 최적해에 Q를 연결
# 선물 갯수 따져봐야 함
for i in range(1, gift_count):
for j in range(1 | (1 << i), 1 << gift_count, 2):
gift_in_hand = 2
for k in range(1, gift_count):
if not(j & (1 << k)):
gift_in_hand += 1
k = dp[i][j] + dist[0][i] * gift_in_hand
if k <= limit:
if res < gift_in_hand:
res = gift_in_hand - 1
print(res)
# 8138: Tourist Attractions
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
inf = int(1e9)
n, m, k = map(int, input().split())
def dijk(s):
hq = []
distance = [inf] * n
distance[s] = 0
heappush(hq, (0, s))
while hq:
d, now = heappop(hq)
if distance[now] < d: continue
for next, new_d in link[now]:
new_d += d
if new_d < distance[next]:
distance[next] = new_d
heappush(hq, (new_d, next))
for i in range(k + 1):
if i == s: continue
dist[s][i] = distance[i]
dist[s][k + 1] = distance[-1]
return 0
def tsp(now, visit):
if dp[now][visit] == 0:
dp[now][visit] = inf
for next in range(k):
if visit & (1 << next): continue
for check in cond[next]:
if visit & 1 << check == 0: break
else:
dp[now][visit] = min(dp[now][visit], tsp(next, visit | (1 << next)) + dist[now + 1][next + 1])
return dp[now][visit]
# 0은 n번 지점
dist = [[inf] * (k + 2) for _ in range(k + 2)]
link = [[] for _ in range(n)]
cond = [[] for _ in range(k)]
from_start = [0] * k
for _ in range(m):
u, v, w = map(int, input().split())
u -= 1; v -= 1
link[u].append((v, w))
link[v].append((u, w))
for _ in range(int(input())):
r, s = map(int, input().split())
r -= 2; s -= 2
cond[s].append(r)
for i in range(k):
cond[i].sort()
for i in range(k + 1):
dijk(i)
dist[-1][i] = dist[i][-1]
for i in range(k):
from_start[i] = dist[0][i + 1]
dp = [[0] * (1 << k) for _ in range(k)]
for i in range(k):
dp[i][(1 << k) - 1] = dist[i + 1][-1]
res = inf
for i in range(k):
if cond[i]: continue
res = min(res, tsp(i, 1 << i) + from_start[i])
if res == inf:
res = dist[0][-1]
print(res)
