(프로그래머스 c++)가장 먼 노드

DFS/BFS에 관한 문제.

DFS도 가능하지만 BFS 방식으로 풀었다.

 

우선 큐가 필요하다.

그리고 방문 여부를 확인하는 bool형 배열 visited, 그래프를 이어주는 bool형 배열 check를 선언하여 false로 초기화.

그리고 depth를 나타내는 int형 배열 dist도 선언하여 0으로 초기화 한다.

 

for문으로 check 배열에 그래프를 이어준다.

사실상 상삼각행렬을 사용한다.

1부터 n까지 상삼각행렬을 그려주도록 하자.

그리고 1부터의 거리를 재야하기 때문에 큐에 1을 넣어주고, visited[1]도 true로 표시.

 

이제 while문으로 q가 비어잇을 때까지 반복한다.

q의 앞부분을 가져오고 pop.

2 ~ n까지 for문을 돌면서

check[현재노드][i] == true && visited[i] == false 이면 아직 방문하지 않은 노드이기 때문에

q에 넣어주고, visited[i] = true로 변환.

그리고 현재 i의 노드는 현재 노드와의 거리가 + 1이므로 dist[i] = dist[node] + 1을 한다.

만약 최대 거리를 나타내는 max값이 dist[i]보다 작으면 max = dist[i] 해주어 변경한다.

 

while문을 빠져나오고 반복문을 통해 1 ~ n까지 dist를 검사하여 max값과 같으면 answer++.

 

전형적인 BFS 형태로 문제를 풀었다..!

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0, max = 0;
    queue<int> q;
    bool visited[20001] = {false, };
    bool check[20001][20001] = {false, };
    int dist[20001] = {0, };
    
    sort(edge.begin(), edge.end());
    
    for(int i = 0; i < edge.size(); i++)
    {
        check[edge[i][0]][edge[i][1]] = true;
        check[edge[i][1]][edge[i][0]] = true;
    }
    
    q.push(1);
    visited[1] = true;
    
    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        
        for(int i = 2; i <= n; i++)
        {
            if(check[node][i] == true && visited[i] == false)
            {
                q.push(i);
                visited[i] = true;
                dist[i] = dist[node] + 1;
                
                if(dist[i] > max)
                    max = dist[i];
            }
        }
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(max == dist[i])
            answer++;
    }
    
    return answer;
}