📍문제
베시와 그녀의 언니 엘시는 정확히 같은 시간에 헛간에서 출발하여 그 둘이 가장 좋아하는 밭에 정확히 같은 시간에 도착하고자 합니다!
농장은 1에서 N까지 번호가 매겨진 N개의 밭(1 <= N <= 16)으로 이루어져 있으며, 밭 1에는 헛간이 위치해 있습니다. 그리고 밭 N은 베시와 엘시가 가장 좋아하는 밭입니다! 농장은 언덕의 한쪽에 위치합니다.
그리고 X < Y일 경우, 밭 X가 밭 Y보다 고도가 높습니다.
M개의 경로가 각 밭들을 짝지은 쌍을 연결하며, 각 경로는 경사가 가파르므로 하산하는 방향으로만 연결할 수 있습니다.
예를 들어, 밭 5와 밭 8을 연결하는 경로는 5 → 8 방향으로 연결할 수는 있지만 반대로는 연결할 수 없습니다. 각 밭의 쌍은 최대 하나의 경로로 연결되며, M <= N(N-1)/2입니다.
베시와 엘시는 이 경로들을 따라 움직일 때에 있어 서로 다른 시간이 걸릴 수 있습니다.
예를 들어, 베시는 10 단위의 시간이 걸릴 수 있고 엘시는 20 단위의 시간이 걸릴 수 있습니다.
또한, 베시와 엘시는 경로 사이를 이동할 때만 시간을 소비합니다. 그들은 서둘러야 하므로 필드를 거치는 동안 거의 시간을 소비하지 않아야 합니다!
당신은 베시와 엘시가 정확히 같은 시간에 가장 좋아하는 밭에 도착하기 위해, 가장 짧은 이동 시간을 파악하는 데 도움을 줘야 합니다.
입력
첫 번째 입력 라인은 N과 M을 공백으로 구분하여 포함합니다.
다음 M개의 라인 각각은 네 개의 정수 A, B, C, D로 경로를 설명합니다. 여기서 A와 B (A < B)는 경로로 연결된 밭을 나타내며, C는 베시가 경로를 따르는 데 필요한 시간이며, D는 엘시가 경로를 따르는 데 필요한 시간을 나타냅니다.
C와 D 모두 1부터 1000 범위 내의 값입니다.
출력
하나의 정수를 출력해야 합니다.
여러분이 출력해야 할 이 정수는 베시와 엘시가 동시에 가장 좋아하는 밭에 도착하는 데 필요한 최소 시간을 나타냅니다.
이것이 불가능하거나 베시나 엘시가 가장 좋아하는 밭에 도달하는 방법이 없는 경우, "IMPOSSIBLE"이라는 단어를 한 줄에 출력합니다.
📍 아이디어
개인적으로 이게 왜 실버3이지? 했던 문제...
아마 영어문제여서 다른 분들이 잘 안 풀어서 그런가 티어가 문제 난도보다 낮게 측정된 게 아닌가 싶었다.
DFS 알고리즘으로 풀었는데, 전체적인 로직은 아래와 같다.
Bessie의 이동 시간 정보를 저장하는 2D 배열과 Elsie의 이동 시간 정보를 저장하는 2D 배열을 선언한 다음
입력에서 각 경로 정보를 읽어서 x, y, bessie, elsie 변수에 할당한다. (x와 y는 연결된 밭의 번호, bessie와 elsie는 Bessie와 Elsie의 이동 시간이다.)
그 후 DFS 함수를 사용해 그래프에서 가능한 경로를 찾는다.
bessieCan 배열에 Bessie가 각 가능한 이동 시간에 도달할 수 있는지 여부를 저장한다. 마찬가지로 elsieCan 배열에 Elsie가 각 가능한 이동 시간에 도달할 수 있는지 여부를 저장한다.
초기에 best 변수를 무한대 값으로 설정한다. 이 변수는 Bessie와 Elsie가 동시에 이동할 수 있는 최적의 이동 시간이다. 만약 이 값이 계속 무한대면 IMPOSSIBLE을 출력하고, 그렇지 않으면 최적의 이동시간을 출력한다.
📍 제출코드
import sys
sys.setrecursionlimit(10**9)
def dfs(graph, dist, curr_node, curr_dist):
if curr_node == n - 1:
dist[curr_dist] = True
return
for a in range(curr_node + 1, n):
if graph[curr_node][a] > 0:
dfs(graph, dist, a, curr_dist + graph[curr_node][a])
n, m = map(int, sys.stdin.readline().rstrip().split())
bessieGrid = [[0] * n for _ in range(n)] # Bessie의 이동 시간 정보를 저장하는 2D 배열
elsieGrid = [[0] * n for _ in range(n)] # Elsie의 이동 시간 정보를 저장하는 2D 배열
for i in range(m):
x, y, bessie, elsie = map(int, sys.stdin.readline().rstrip().split()) # 입력에서 각 경로 정보를 읽어서 x, y, bessie, elsie 변수에 할당
# x와 y는 연결된 밭의 번호, bessie와 elsie는 Bessie와 Elsie의 이동 시간
x -= 1
y -= 1
bessieGrid[x][y] = bessie
elsieGrid[x][y] = elsie
# 가능한 이동 시간을 나타내는 불리언 배열
# bessieCan은 Bessie가 각 가능한 이동 시간에 도달할 수 있는지 여부 저장, elsieCan은 Elsie가 각 가능한 이동 시간에 도달할 수 있는지 여부 저
bessieCan = [False] * 20000
elsieCan = [False] * 20000
dfs(bessieGrid, bessieCan, 0, 0)
dfs(elsieGrid, elsieCan, 0, 0)
# 초기에 best 변수를 무한대 값으로 설정. 이 변수는 Bessie와 Elsie가 동시에 이동할 수 있는 최적의 이동 시간
best = float('inf')
for i in range(len(bessieCan)):
if bessieCan[i] and elsieCan[i]:
best = i
break
# best가 여전히 무한대 값인 경우 "IMPOSSIBLE"을 출력하고, 그렇지 않으면 최적의 이동 시간을 출력
if best == float('inf'):
print("IMPOSSIBLE")
else:
print(best)
