[프로그래머스 Level 3] [그래프] 가장 먼 노드 (C++)

안녕하세요! 코딩하는 경제학도 쏘코입니다.

오늘부터는 고득점 KIT의 마지막 주제인 그래프 문제를 풀어보겠습니다.

맨 뒤에 있는 주제라서 소홀하기 쉽지만 제가 예전에 본 코딩테스트 문제에서도 그래프 문제가 꽤 자주 등장했기에 쉽게 넘어가서는 안된다고 생각하는 주제가 바로 그래프입니다.

가장 다양한 자료구조와 알고리즘을 이용한 PS주제가 그래프이지 않을까 조심스럽게 생각해보면서 문제 설명으로 바로 들어가도록 하겠습니다!

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3

programmers.co.kr

0. 문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

0.0. 제한사항

노드의 개수 n은 2 이상 20,000 이하입니다.
간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

0.1. 입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

0.2. 입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

1. 풀이 과정

문제를 딱 보자마자 최단경로를 보고 BFS로 풀면 되겠다는 생각이 들었습니다. 바로 queue를 준비하고 while(!q.empty()) 구문을 작성할 준비를 해야합니다.

먼저 연결 여부를 확인하는 배열, 방문 여부를 확인하는 배열, 거리를 확인하는 배열까지 총 3개의 배열을 만들어줍니다. 각각 false, false, 0으로 초기화를 했습니다. 또한 BFS를 사용할 것이었기 때문에 당연히 int형태의 queue를 하나 만들었습니다.

그리고 연결 여부를 확인하는 배열에다가 edge에서 받아온 정보를 바탕으로 true값을 넣습니다. 간선이 양방향이라는 것을 확인했다면 당연히 index의 앞뒤를 바꾼 배열에도 true값을 할당해줘야 합니다.

while문에 들어가기 전에 queue에 1을 넣어줍니다. 우리는 1부터 거리를 재기 시작할 것이기 때문이죠.

while문은 BFS를 구현한 부분입니다. 먼저 queue의 맨 앞부분을 추출합니다.

그리고 for문을 통해 추출한 값과 연결된 노드를 확인합니다. 만약 연결은 되어있는데 아직 방문을 하지 않았다면 그 노드를 queue에 넣고, 방문했음을 표시하고 거리값을 부여합니다. 거리는 distance[출발 위치 index]에 +1한 값을 부여합니다. while문은 이게 끝입니다.

그 다음은 max값을 구합니다. distance 배열 내에서 최대값을 구하기 위해서는 max_element()함수가 필요한데, 이걸 사용하기 위해서 algorithm을 include합니다.

max_element() 함수는 주소값을 반환하기 때문에 포인터 표시를 해 주는 것을 잊지 맙시다!!

마지막으로 for문을 돌려서 max과 일치하는 distance의 값이 몇개가 존재하는지 확인하고 answer에 할당합니다. 그럼 정답이 나옵니다!

2. 소스 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n^2)
    사용한 알고리즘: BFS(너비 우선 탐색), 그래프
    사용한 자료구조: vector, queue
    
    논리 :
    먼저 연결되었는지 확인하기 위한 bool변수를 담은 2차원 배열과 방문 여부를 담은 1차원 배열을 만든다.
    그리고 1번 node로부터의 거리를 담은 1차원 배열도 만든다.
    그리고 BFS를 사용하기 위해서 queue를 사용한다.
    
    먼저 for문을 통해 2차원 배열에 값을 채워준다. 간선이 양방향이라고 나와있으므로, 벡터의 앞과 뒤를 바꿔서도 배열에 넣어주어야 한다.
    그 다음 queue에 1을 넣어주고 BFS를 위해 while문을 돌린다.
    2번부터 순서대로 확인해서 노드가 연결되어있고, 아직 방문하지 않았다면 queue에 넣고, 방문여부를 체크해준다.
    그리고 거리를 담은 배열의 i번째 index에 현재 노드의 거리에 1을 더해준 값을 넣는다.
    
    이 작업을 반복하고 나서 queue가 비면 while문이 종료된다.
    이제 거리를 담은 배열에서 최대값을 구하고, 그 값과 같은 idx가 몇 개가 있는지 확인하고 그 값을 return한다.
*/

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    queue<int> q; // 임시 queue
    bool linkchk[20001][20001] = {false}; // 연결 여부 확인 배열
    bool visited[20001] = {false}; // 방문 여부 확인 배열
    int distance[20001] = {0}; // 거리 배열
    
    for (int i = 0; i < edge.size(); ++i){ // 연결 여부 linkchk에 할당
        linkchk[edge[i][0]][edge[i][1]] = true;
        linkchk[edge[i][1]][edge[i][0]] = true;
    }
    
    // 출발위치인 1 삽입
    q.push(1);
    visited[1] = true;
    
    // BFS
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        
        for(int i = 2; i <= n; ++i){ // 2부터 n까지 다 넣어보기
            if(linkchk[temp][i] == true && visited[i] == false) { // 길은 있는데 아직 방문은 안했다
                q.push(i);
                visited[i] = true;
                distance[i] = distance[temp]+1; // 도착노드의 거리값은 출발노드의 거리값에 1을 더해준다
            }
        }
    }
    
    int max = *max_element(distance, distance+n+1); // 거리의 최대값 구하기
    
    for (int i = 2; i <= n; ++i){ // 최대값의 개수 구하기
        if(max == distance[i])
            ++answer;
    }
    
    return answer;
}