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

문제:

https://school.programmers.co.kr/learn/courses/30/lessons/49189

 

풀이 : 

- BFS를 사용해 풀었으며, 양방향간선인데 각 간선은 [1,2], [3,2]처럼 순서 상관없이 주어졌으므로, 각 행의 0번 좌표와 1번좌표를 모두 찾아 이어진 노드를 찾을 필요가 있었다. 

 - board 배열을 선언하여 1번노드로부터 떨어진 거리를 저장하도록 한다. 

 - board 배열의 최댓값을 따로 저장하고, board를 순회하며 이값과 일치하는 횟수를 저장하여 출력한다. 

 

코드 : 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

int board[20002];
bool visit[20002];
queue <int> q;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    q.push(1);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        visit[cur] = 1;
        for(int i = 0; i < edge.size(); i++){
            if(edge[i][0] == cur && !visit[edge[i][1]]){
                q.push(edge[i][1]);
                board[edge[i][1]] = board[cur]+1;
                visit[edge[i][1]] = 1;

            }
            else if(edge[i][1] == cur&& !visit[edge[i][0]]){
                q.push(edge[i][0]);
                board[edge[i][0]] = board[cur]+1;
                visit[edge[i][0]] = 1;
            }
        }
    }
    int mx= *max_element(board, board + n);
    for(int i = 1; i <= n; i++){
        if(mx == board[i])
            answer ++;
    }
    return answer;


}

 

  PS. 백준만하다가 프로그래머스를 해봤는데, 문제가 훨씬 깔끔해서 좋은것 같다...