[백준 18352] - 특정 거리의 도시 찾기(C++)

📕문제

---

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

📕입력

---

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

📕출력

---

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

🔎문제 해석

---

문제에서 주어지는 변수가 많아서 헷갈릴 수 있는 문제다.

• N : 정점의 개수
• M : 도로(간선)의 개수
• X : 출발도시의 숫자
• K : 출발 도시에서 도착지점 까지의 목표 거리
  • X->N까지의 거리가 K이면 N은 정답인 도시

문제를 보면 각 도로의 길이는 1로 고정되어 있다.

이런 문제를 푸는 방법은 여러 가지가 있지만, 나는 우선순위 큐를 이용한 다익스트라 알고리즘으로 풀었다.

다익스트라 알고리즘은 우선순위큐를 사용하는 것이 굉장히 보편적인 방식이다.

📃초기 풀이 방식

---

• 변수 선언
  • graph : 입력 행렬
  • visit : 각 도시의 방문 처리를 하는 배열
  • length : 출발지점에서 각 도시까지의 길이를 저장하는 배열
  • pq : 우선순위큐(거리,도시)로 거리가 짧은 도시가 우선순위로 정렬됨.
• 인접행렬로 입력받아서 graph[start][finish]=1로 선언함.
• 입력이 끝난뒤에 pq에 (0,x) 0은 출발지점에서 x까지의 거린데 x가 출발지점이기에 0을 넣음.
• length[x]을 0으로 초기화함.
• 다익스트라 함수 실행
  • 우선 큰 맥락은 PQ가 빌때까지 진행함.
  • PQ에 top을 추출해서 first를 distance로, second를 vertex로 선언.
  • pq를 pop한 후에 visit[vertex]를 방문처리(=1로 선언)
  • 반복문으로 모든 벌텍스에 대해서 검사했음.
    • 간선이 있거나, 방문처리를 하지 않았다면 pq에 넣고, 거리를 최신화해줬음.
• 함수를 빠져나온뒤에 length 배열에서 k를 찾아내서 출력함.

🛑문제점

---

이러한 방식으로 문제를 푸니 메모리초과와 시간 초과가 발생했다.

당연히 n+1 * n+1에 행렬과, 한번 방문할때마다 간선이 있는지 없는지를 처음부터 끝까지 체크하니까 시간 초과가 발생한 것이다. 

그래서 나는 인접리스트를 사용하기로 했다.

인접 리스트는 인접 행렬과 개념은 비슷하지만, 내가 그 index에 대해서 가지고 있는 원소 개수만큼만 배열을 할당하기에 인접 행렬보다 효과적이라고 할 수 있다.

📜수정된 풀이 방식

---

• 초기 풀이 방식과 거의 동일한데 변수선언에서 graph부분만 다르다.
• 다익스트라부터도 세부적인것은 비슷하고 살짝살짝만 다르다.
  • 우선 반복문에 대해서 검사하는 횟수가 확연히 줄어들었다.
  • 1번도시부터 n번도시까지 검사하는것이 아닌 인접리스트를 사용했기에 간선이 있는 도시에 대해서만 검사했다.
  • 거기서 그 도시가 아직 방문하지 않았다면(visit[v]==0) 길이를 비교해야 한다.
  • 만약 길이가 현재 저장된 길이인 length[v] vs distance+1(각 도로의 길이가 1이기에) 와 비교해서 만약 기존 배열이 더 큰 길이라면 길이를 업데이트 해주고, pq에 푸쉬한다.
  • 현재 저장된 길이가 더 작다면 아무일도 일어나지 않는다.
• 다익스트라를 빠져나온뒤에는 만약 length[i]가 k인 도시가 있다면 bool 변수인 check를 true로 초기화하고, 그 도시를 출력한다.
• 만약 check가 false라면 k인 도시가 하나도 없다는 뜻이기에 -1을 출력함.

 

💻코드

/*
실버2 특정거리의 도시 찾기
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;
int n, m, k, x;
queue<int> q;
vector<int> graph[300001];
vector<int> length;
vector<int> visit;
#define INF INT_MAX
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // pair의 첫번째 순으로 정렬됨.
void dijkstra();
int main()
{
    bool check = false;
    cin >> n >> m >> k >> x;
    visit.resize(300001, 0);
    length.resize(300001, INF);
    // n : 정점의 개수 m : 간선의 개수 k : 정답인 거리 , x : 출발
    for (int i = 0; i < m; i++)
    {
        int start, finish;
        cin >> start >> finish;
        graph[start].push_back(finish);
    }
    pq.push(make_pair(0, x)); // first에는 거리. second에는 출발지역이 들어가용~
    length[x] = 0; //출발점 거리는 0
    dijkstra();
    for (int i = 1; i <= n; i++)
    {
        if (length[i] == k) //k길이를 만족한다면 그때의 vertex를 출력
        {
            check = true;
            cout << i << endl;
        }
    }

    if (check == false) //만약 k길이를 만족하는 경로가 없다면 -1출력 
    {
        cout << -1 << endl;
    }
}
void dijkstra()
{
    //거리 테이블 최신화 끝
    while (!pq.empty())
    {
        auto temp = pq.top();
        int distance = temp.first; //거리 추출.
        int startVertex = temp.second; //출발지 추출.
        visit[startVertex] = 1;
        pq.pop();
        for (int i = 0; i < graph[startVertex].size(); i++)
        {
            int v = graph[startVertex][i];        
            if (visit[v] == 0) //방문을 하지 않았다면.
            {
                if (length[v] > distance + 1) //기존 pq에 푸쉬한 length보다 더 작은 길이라면 
                {
                    length[v] = distance + 1; //length[v]를 업데이트해줌.
                    pq.push(make_pair(length[v], v)); //pq에 넣어줌.
                }
                else if (length[v] <= distance + 1) //만약 기존에 길이보다 크다면 굳이 pq에 넣어줄 필요가 없음.
                {
                    continue;
                }
            }
        }
    }
}

✔느낀점

• 인접 행렬과 인접 리스트를 따로 구분하지 않고 모든 알고리즘을 인접행렬로 풀이했었는데, 인접리스트 방식도 굉장히 효율적인 방식이라는 것을 깨달았다.
• pq에 사용 방식은 사용할수록 헷갈린다. 
• 굳이 다익스트라 알고리즘이 아니어도 풀 수 있을 문제이긴 했다.