PS 일지

문제https://www.acmicpc.net/problem/5214$N$개의 역과 $M$개의 하이퍼튜브가 존재하며, 하이퍼튜브 하나는 역 $K$개를 서로 연결한다.$1$번 역에서 $N$번 역으로 가는데 방문하는 최소 역의 수를 구해보자. 풀이하나의 하이퍼튜브가 연결하는 $K$개의 역을 서로 모두 이어주게 된다면, 간선이 $\dfrac{K(K-1)}{2}$개 생기게 된다.아래는 2, 4, 5, 7, 8, 9번 역을 연결하는 하이퍼튜브를 그래프에 추가시킨 그림이다.이 방식대로 그래프를 구성한다면 전체 간선은 $O(MK^2)$만큼 생기게 되고, 이는 메모리나 시간의 제약으로 인해 불가능한 풀이가 된다.하이퍼튜브 하나를 그래프의 새로운 가상의 정점으로 본다면 어떨까?하나의 하이퍼튜브로 인해 추가되는 간선은 $..

시작하기 전에그래프에서 최단 경로를 찾는 알고리즘은 크게 세 가지가 존재한다고 알고 있었다. Dijkstra- 시작점이 존재해야 함. 그래프의 간선 가중치가 음이 아닌 정수일 때만 가능Floyd-Warshall- 모든 정점 쌍 사이의 최단 경로를 구할 때 사용, 음수 가중치 및 음의 사이클 판별 가능Bellman-Ford- 시작점이 존재해야 함. 음수 가중치 및 음의 사이클 판별 가능 Claude 선생님과 함께 알고리즘 복습을 하던 중에 SPFA라는 것을 접하게 되었다.SPFA 또한 그래프에서 최단 경로를 찾는 알고리즘이며, 이를 알기 위해선 Bellman-Ford를 먼저 알아야 한다.여기서는 Bellman-Ford의 원리만 간단히 설명하겠다.Bellman-Ford정점이 $N$개인 그래프의 어떤 최단 경..

문제https://www.acmicpc.net/problem/9376두 명의 죄수가 $H \times W$ 크기의 감옥에 갇혀 있다.감옥을 구성하는 격자 칸은 빈 칸('.'), 벽('*'), 문('#'), 죄수('$')로 이루어져 있다.두 죄수가 모두 감옥의 바깥으로 탈출하기 위해 열어야 하는 문의 최소 개수를 구하는 문제이다.풀이문의 개수가 충분히 적다면 문의 열림/닫힘 상태를 관리하는 비트마스킹 + BFS로 해결할 수 있으나, 이 문제에서는 먹히지 않는다. 답이 나올 수 있는 경우를 두 가지로 나눠보았다.1. 두 명의 죄수가 만나지 않고 각각 탈출하는 경우각 죄수를 시작점으로 두고 다익스트라 혹은 0-1 BFS로 탈출하는 최단 경로를 구한다.2. 두 명의 죄수가 만나서 같이 탈출하는 경우첫 번째 죄수..