Dalin's Archive

https://www.acmicpc.net/problem/10282 컴퓨터 간 의존성이 주어진다. a가 b를 의존하면, b가 감염되면 a도 감염된다는 뜻이다. b가 감염된 후 a가 감염될 때까지의 시간도 알려준다. 해킹 당한 컴퓨터를 알려주면, 그 컴퓨터를 포함해서 총 몇 대가 감염되는지, 얼마나 시간이 걸리는지 구해야 한다. 처음에는 서로 연결되었는지 봐야 하니까 유니온 파인드가 잠깐 떠올랐다가, 얼마나 시간 걸리는지도 체크해야 하니까 접었다. 고민하다 보니 플로이드 워샬이 떠올랐다. 한 컴퓨터에서 다른 컴퓨터로 연결되는지, 해킹될 때까지 얼마나 시간이 걸리는지를 구할 수 있으니까 !! (플로이드 워샬로 해도 답은 나오잖아요 ? 메모리, 시간이 문제지..) 풀이 생각난 게 신나서 풀었다.. 예제는 풀리..

문제 보러 가기! 평범한 다익스트라 + 알파이다. 최소 비용을 가지는 경로를 방문 도시 순서대로 출력하는 부분, 그 경로에 포함되는 도시 개수도 출력해야 해서 좀 더 생각해야 했다. distance 리스트를 활용했다. 평범한 다익스트라에서는 distance 리스트는 출발점에서 그 점까지의 비용만 저장한다. 그런데 여기에서는 출발점에서 그 점까지 최소 비용으로 올 때, 그 전 점도 저장했다! 다익스트라를 다 수행한 후에, 최종 도착 점부터 distance 리스트를 활용해서 거꾸로 봐주었다. 그 전에 어떤 점에서 왔는지를 봐서 history 리스트에 저장한 후, 거꾸로 출력했다. [TMI 잠깐 근황] 요즘 싸피에서 프로젝트를 열심히 하느라고 ㅠㅠ 문제를 별로 못풀다가 푸니까 재밌다 >< (물론 프로젝트도....

문제 보러 가기! ㅎㅎ제목부터 재밌다. (TMI: 나도 젤다의 전설 바람의 숨결! 게임을 종종 한다 ㅎㅎ ) 전에 나는 평범한 다익스트라 문제만 풀어봤는데, 조금 응용한 문제를 풀어봐서 재밌었다. 시작하는 점이 정해져 있고(제일 왼쪽 위), 음의 간선이 없으니까 다익스트라가 가능하다. 다익스트라는 특정 노드에서 시작해서, 다른 노드로 가는 최단 경로를 각각 구해준다. 이 문제는 잃은 도둑 루피가 최소로 되도록! 0,0 점에서 N-1,N-1까지 이동해야 한다. 조금 주의할 것이 있다고 하면~ 1차원 리스트로 최단 경로 테이블을 만들기 위해서, i좌표와 j 좌표를 곱해서 만든 하나의 숫자로 인덱스 위치를 표현했다. 상하좌우로 갈 때도 그 하나의 숫자를 바꿔줘야 한다. (위: -N, 아래: N, 왼쪽: -1,..

문제 보러 가기! N개의 집(정점)이 주어지고, 집과 집을 연결하는 도로(간선)가 주어진다. 도로는 단방향 간선이고, 이동하는 데 걸리는 시간이 주어진다. 도로는 모든 집들 간의 이동이 가능하게 했다. 모든 집에서 생일을 맞은 인수의 집으로 오고 가는데, 이때 오가는 시간이 가장 오래 걸리는 집이 얼마나 걸리는지 구하는 문제이다. 그러면 인수네 집 -> 다른 모든 집으로 가는 데 드는 최소 시간도, 다른 모든 집 각각에서 인수네 집으로 가는 데 드는 최소 시간도 모두 알아야 한다. 인수네 집에서 다른 모든 집들 가는 최단 경로는 다익스트라로 할 수 있다는 건 처음부터 알았다. 다른 각각의 집에서 인수네 집으로 가는 최단 경로는 어떻게 구할까.. 그게 고민이었다. 처음에는 마음 편하게 ! 모든 정점 간의 ..

문제 보러 가기! 아이디어 라고 할 것도 없는 것 같다. 다익스트라로 풀었다.. 다익스트라..는 전에도 들어는 봤지만, 딱히 공부하지는 않았었다. 이번 기회에 다익스트라를 공부할 수 있었다! 참고한 자료 안경잡이 개발자님의 글과 레드캐럿님의 벨로그 포스팅!!. 안경잡이 개발자님은 영상으로도 있어서, 다익스트라가 뭔지 이해하는 데 도움이 되었고, 레드캐럿님의 벨로그 포스팅은 파이썬 코드라서 코드 구현을 어떻게 해야 할지 알 수 있었다!! 또 플로이드워셜과의 차이점도 궁금했는데, 잘 설명해주셔서 좋았다 ㅎㅎ 코드 👩‍💻 import heapq import sys input = sys.stdin.readline V, E = map(int, input().split()) # 노드 개수, 간선 개수 start =..