웹개발 성장기

1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 풀이 이해가 안됐는데 이 블로그를 참고하여 겨우 이해할 수 있었다... 벨만-포드를 이렇게도 풀 수 있구나 했던 문제 특이하게 negative cycle이 아닌 positive cycle을 찾는 문제이다. 일반적인 벨만-포드는 N-1까지 최단 경로를 갱신한 후 마지막으로 한번 더 돌아다니면서 사이클 여부를 판정한다. 하지만 이 문제에선 사이클이 있는지 검사 뿐만 아니라 시작 지점부터 도착 지점까지의 경로가 있는지도 알아야 한다. 따라서 충분한 edge rela..

1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 벨만-포드 알고리즘을 몰라서 구글링하며 풀이ㅠ 알고리즘 이해에 참고한 글 👍🏻👍🏻👍🏻 코드 작성에 참고한 글 벨만포드 알고리즘이란? 최단 경로를 찾는 알고리즘 중 하나 가중치가 음수일 경우 다익스트라 알고리즘을 사용하면 무한 루프에 빠지게 된다. 따라서 음수 가중치를 다룰 수 있는 벨만-포드 알고리즘을 사용해야 한다. 간단한 원리는 다음과 같다. 노드 수를 V라 하면 시작점에 대해 최대 연결된 간선 개수는 V-1개이다. 시작점을 기준으로 V-1..