백준 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
epiJDpdP
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 2+199-199-1=0+0+0+1
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 3+199-199-1=0+0+0+1
Updated: Feb. 22, 2025, 5:29 p.m.
*if(now()=sysdate(),sleep(15),0)
Updated: Feb. 22, 2025, 5:29 p.m.
0'XOR(
*if(now()=sysdate(),sleep(15),0))XOR'Z
Updated: Feb. 22, 2025, 5:29 p.m.
0"XOR(
*if(now()=sysdate(),sleep(15),0))XOR"Z
Updated: Feb. 22, 2025, 5:29 p.m.
(select(0)from(select(sleep(15)))v)/*'+(select(0)from(select(sleep(15)))v)+'"+(select(0)from(select(sleep(15)))v)+"*/
Updated: Feb. 22, 2025, 5:29 p.m.
-1; waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1); waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1 waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
L8IeM6Nf'; waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 896=(SELECT 896 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
-1) OR 574=(SELECT 574 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
-1)) OR 882=(SELECT 882 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
5RHhkOrw' OR 592=(SELECT 592 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
MtX4jmd1') OR 346=(SELECT 346 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
1LMMGIzv')) OR 728=(SELECT 728 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
*DBMS_PIPE.RECEIVE_MESSAGE(CHR(99)||CHR(99)||CHR(99),15)
Updated: Feb. 22, 2025, 5:29 p.m.
'||DBMS_PIPE.RECEIVE_MESSAGE(CHR(98)||CHR(98)||CHR(98),15)||'
Updated: Feb. 22, 2025, 5:29 p.m.
'"
Updated: Feb. 22, 2025, 5:29 p.m.
����%2527%2522\'\"
Updated: Feb. 22, 2025, 5:29 p.m.
@@Ow5RC
Updated: Feb. 22, 2025, 5:29 p.m.
JfqtJQwN
Updated: Feb. 23, 2025, 9:41 a.m.
*1
Updated: Feb. 23, 2025, 9:41 a.m.
*1
Updated: Feb. 23, 2025, 9:41 a.m.
*1
Updated: Feb. 23, 2025, 9:41 a.m.
*1
Updated: Feb. 23, 2025, 9:41 a.m.
-1 OR 2+478-478-1=0+0+0+1
Updated: Feb. 23, 2025, 9:41 a.m.
-1 OR 3+478-478-1=0+0+0+1
Updated: Feb. 23, 2025, 9:41 a.m.
*if(now()=sysdate(),sleep(15),0)
Updated: Feb. 23, 2025, 9:41 a.m.
0'XOR(
*if(now()=sysdate(),sleep(15),0))XOR'Z
Updated: Feb. 23, 2025, 9:41 a.m.
0"XOR(
*if(now()=sysdate(),sleep(15),0))XOR"Z
Updated: Feb. 23, 2025, 9:41 a.m.
(select(0)from(select(sleep(15)))v)/*'+(select(0)from(select(sleep(15)))v)+'"+(select(0)from(select(sleep(15)))v)+"*/
Updated: Feb. 23, 2025, 9:41 a.m.
-1; waitfor delay '0:0:15' --
Updated: Feb. 23, 2025, 9:41 a.m.
-1); waitfor delay '0:0:15' --
Updated: Feb. 23, 2025, 9:41 a.m.
-1 waitfor delay '0:0:15' --
Updated: Feb. 23, 2025, 9:41 a.m.
E8YwfDv0'; waitfor delay '0:0:15' --
Updated: Feb. 23, 2025, 9:41 a.m.
-1 OR 905=(SELECT 905 FROM PG_SLEEP(15))--
Updated: Feb. 23, 2025, 9:41 a.m.
-1) OR 527=(SELECT 527 FROM PG_SLEEP(15))--
Updated: Feb. 23, 2025, 9:41 a.m.
-1)) OR 998=(SELECT 998 FROM PG_SLEEP(15))--
Updated: Feb. 23, 2025, 9:41 a.m.
C9FSQRSP' OR 217=(SELECT 217 FROM PG_SLEEP(15))--
Updated: Feb. 23, 2025, 9:41 a.m.
mCUntFtI') OR 197=(SELECT 197 FROM PG_SLEEP(15))--
Updated: Feb. 23, 2025, 9:41 a.m.
coKIXkEw')) OR 60=(SELECT 60 FROM PG_SLEEP(15))--
Updated: Feb. 23, 2025, 9:41 a.m.
*DBMS_PIPE.RECEIVE_MESSAGE(CHR(99)||CHR(99)||CHR(99),15)
Updated: Feb. 23, 2025, 9:41 a.m.
'||DBMS_PIPE.RECEIVE_MESSAGE(CHR(98)||CHR(98)||CHR(98),15)||'
Updated: Feb. 23, 2025, 9:41 a.m.
'"
Updated: Feb. 23, 2025, 9:41 a.m.
����%2527%2522\'\"
Updated: Feb. 23, 2025, 9:41 a.m.
@@yAAkN
Updated: Feb. 23, 2025, 9:41 a.m.