백준 13913번 숨바꼭질 4 - C++ 풀이
1. BFS를 이용하여 K까지 가기 위한 최단 거리를 찾는다. 2. BFS 과정에서 이전 노드를 기록하여 경로를 구할 수 있도록 한다. 1. BFS를 이용하여 K까지 가기 위한 최단 거리를 찾는다. 수 하나를 노드 하나라고 생각하고, n번 노드와 [n+1, n-1, 2n]번 노드는 간선으로 이어져있다고 생각하면 된다. BFS를 이용하여 N번 노드에서 K번 노드까지의 거리를 구한다. 이때 노드 번호의 범위를 [0, 200000]으로 제한할 수 있다. N, K의 범위가 100,000이므로 거리의 최댓값은 100,000이다. 그런데 200,000보다 큰 노드의 경우 더 작아지는 방법은 -1 밖에 없기 때문에 최소 100,000번의 연산을 해야 K로 갈 수 있다. 따라서 200,000을 넘어가는 수는 고려하지 ..
2022. 8. 17.
백준 5214번 환승 - C++ 풀이
1. 하이퍼 튜브도 노드로 생각한다. 2. 일반 노드 -> 하이퍼 튜브 노드로 가는 간선의 가중치는 0으로 처리한다. 3. BFS를 이용해 1번 정점과 N번 정점 사이의 거리를 구한다. 1. 하이퍼튜브도 노드로 생각한다. 하나의 하이퍼튜브로 연결된 K개의 노드들을 전부 간선으로 이어주려면 O(KM^2)의 시간 복잡도와 공간 복잡도가 필요하다. K, M이 최대 1,000이므로 이 방법은 사용할 수 없다. 대신 하이퍼 튜브를 가상의 노드로 생각하는 방법을 사용한다. 하이퍼 튜브 H로 노드 1, 2, 3이 연결되어있다면 1, 2, 3번 노드 사이에 간선을 추가하지 않고 H번 노드와 각각 1, 2, 3번 노드로 가는 간선 3개 H-1, H-2, H-3만 추가해준다. 결과적으로 1, 2, 3번 노드 사이에 이동이..
2022. 8. 1.
