Algorithm

백준 1507번: 궁금한 민호 (python)

by VICENTE97P4

Jan. 29, 2022, 12:59 p.m.

문제 링크: https://www.acmicpc.net/problem/1507

오랜만에 씁니다.

사실 저번에 buffer와 spool에 대해서 한 시간에 걸쳐서 포스팅 중이었는데.. 실수로 날리는 바람에..

힘들어서 업데이트 하지 않았습니다.

연초에 정말 바빴습니다. 계절학기 + 사회봉사(죄를 지어서 그런게 아니고, 졸업 필수 요건입니다..) + 면접 준비

이 모든게 2주 동안 몰려있어서 너무 정신없었습니다.

그리고 삼성 알고리즘 캠프도 지원했었는데 그건 파이썬을 지원해주지 않아서 문제를 풀지 못했습니다..

삼성은 유난히 C랑 JAVA를 좋아하는 것 같네요.. JAVA 공부도 다시 해야겠습니다. 삼성전자.. 도대체 그곳은..

아무튼 오늘은 플로이드 와샬 문제를 풀어보겠습니다.

문제를 요약하자면 이미 각 지점까지의 최단거리를 알고있을 때, 도로 개수를 최소한으로 설정했을 때,

그 도로를 건너는데 필요한 시간을 모두 합한 값을 구하는 것입니다.

처음에 이 문제를 읽고 '이게 무슨 플로이드 와샬이지?' 하는 생각이 들었습니다.

뭘 어쩌라는 건지.. 내가 플로이드 와샬에 대해 뭘 잘못 알거나 덜 알고 있나? 하는 생각도 들고,

경우의 수가 너무 많은데? 이걸 일일히 커버하는게 맞나..? 하는 생각도 들었습니다.

결국 문제풀이의 핵심은 도시에서 도시로 가는 모든 최소 도로들을 일단 다 설치하고, 없어도 최단시간이 같은 도로를 없애는 것입니다.

코드를 보겠습니다.

import sys;

input = sys.stdin.readline
N = int(input().strip())
graph = [list(map(int, input().split())) for _ in range(N)]
discard = [[False] * N for _ in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j or j == k or i == k:
                continue
            if graph[i][j] == graph[i][k] + graph[k][j]:
                discard[i][j] = True

            elif graph[i][j] > graph[i][k] + graph[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if not discard[i][j]:
            ans += graph[i][j]
print(ans)

길었던 고민과 달리, 풀이는 엄청 간단합니다.

플로이드 와샬은 모든 도시가 어느 한 도시를 거쳐서 가는 경우에 최단 시간을 구하는 겁니다.

여기서 중간에 거치는 도시는 제일 바깥쪽 for문인 k 변수에 해당하죠.

그럼 어차피 모든 지점과 도로를 다 따져볼거니까 i-j를 잇는 도로와 i-k-j를 통하는 도로의 최단 시간을 비교해서

같으면 i-j를 잇는 도로를 없애는 겁니다. 어차피 i-k-j를 통해서 i->j로 갈 수 있는데 i-j 직통 도로가 또 있을 필요는 없으니까요.

아래는 해당 부분을 구현한 코드입니다.

            if graph[i][j] == graph[i][k] + graph[k][j]:
                discard[i][j] = True

여기서는 구현의 편의성을 위해 버리는 도로를 discard로 기록했습니다.

플로이드 와샬 알고리즘은 모든 도시와 모든 도로를 싹 다 체크하기 때문에 이 방법을 이용하면 필요한 최소 도로를 구할 수 있습니다.

그런데 문제를 끝까지 잘 읽어보면 불가능한 경우에 대해서도 생각해야합니다.

사실 개인적으로 이 부분은 좀 불친절하지 않나 생각합니다. 불가능한 경우에는 어떤 것들이 있는지 파악하기 힘들기 때문이죠.

불가능한 경우는 주어진 도시와 도시 사이의 최단 시간보다 다른 도시를 거쳐가는 경우의 최단 시간이 더 짧은 경우입니다.

예를 들어 1번 도시와 2번 도시 사이의 최단시간은 5로 주어졌는데 1->3은 1, 3->2는 2로 주어져서 1->3->2는 3인 경우입니다.

그림을 그려봤는데 너무 조잡하네요.. 어떻게 하면 깔끔하게 잘 그릴 수 있으려나..

암튼 이러한 경우에 불가능하므로 -1을 출력하면 됩니다. 아래는 해당 부분 코드입니다.

elif graph[i][j] > graph[i][k] + graph[k][j]:
                print(-1)
                exit()

마지막으로, 버려지지 않은 도로들의 시간을 모두 더해주면 정답입니다.

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if not discard[i][j]:
            ans += graph[i][j]
print(ans)

여기서 주의할 점은, 양방향 도로이기 때문에 모든 graph의 값을 다 더하면 안 된다는 겁니다.

딱 반만 더해야죠..

코드 자체는 간단하지만 아이디어가 꽤 어렵기 때문에 개인적으로는 골드 1에서 플레 5까지도 줄 수 있다고 생각합니다.

인풋값이 너무 작아서 다른 기믹을 쓸 수도 있다고 합니다.

예를 들어 최소 거리를 하나씩 두면서 플로이드 와샬을 쓴다던가 하는 방법 등이 있다고 하는군요..

인풋을 한 200정도로 늘리고 난이도를 올리는게 좋을 것 같다는 생각이 듭니다.

이대로 낮은 티어를 받기에는 아까운 문제입니다.

이런 아이디어를 떠올리는게 힘들다면 어떻게 해야 할까요?

사실 이 영역은 타고난 지능의 영역이라 생각합니다.

그럼 저같이 평범한 사람은 어떻게 해야 할까요? 그냥 이런 문제가 나오면 포기해야 할까요?

저도 사실 잘 모르겠습니다.. 이게 답이 있다면 벌써 누군가 널리널리 알렸겠죠..

그냥 1~2시간 생각해보고 모르겠으면 다른 사람들의 풀이를 보고 이러한 아이디어를 최대한 많이 배워보려고요.

세상에 나와있는 모든 기출 아이디어만 다 알아도 어딘가에 쓸 수 있지 않을까요?

하루하루 열심히 배워가야겠습니다.

백준 floyd-warshall 52 view 730