[프로그래머스 49189] 가장 먼 노드

문제링크

programmers.co.kr/learn/courses/30/lessons/49189

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

 

문제난이도

Level 3

 

문제풀이

1. 연결노드 정보에 따라 각 노드별 인접노드 정보를 vector에 저장

    ex. [1, 3] -> vc[1] = 3, vc[3] = 1

         1번은 3번과 연결 되어있으며 반대로 3번도 1번과 연결되어 있다

2. 1번 노드에서 출발(방문표기)

3.-1. '현재 노드에서 1번 노드까지 도달하는거리 > 현재 구한 노드 1번 노드까지 도달하는 최대거리' 이러한 경우,

      최대값을 갱신해주고 1번으로부터 먼 노드 cont를 1로 초기화 해준다

3-2. '현재 노드에서 1번 노드까지 도달하는거리와 현재 구한 노드 1번 노드까지 도달하는 최대거리' 이러한 경우,

      1번으로부터 먼 노드 cont를 1개 증가시켜 준다

4-1. 현재 노드의 방문하지 않은 인접노드들을 큐에 추가하고 방문표기를 한다

4-2. 현재 노드에서 1번 노드까지 가는 최댄거리 +1을 하여 인접노드서 1번 노드까지 가는 거리를 갱신한다

 

주의사항

1. 시간초과로 골치아픈 문제다.. 계획을 잘 세워서 풀기 시작해야한다

2. DFS의 풀이경우,  (1, 2) , (1, 3), (2, 3) 이렇게 연결되있을 때 깊이우선에 따라, 1 -> 2 -> 3으로 방문한다

이렇게 탐색하는 경우, 3번노드에서 1번노드를 방문하는 거리는 2로 나타난다

하지만 1번노드와 3번노드 연결되어있기 때문에 최단거리는 1이된다

DFS로 풀이 시, 이러한 점을 주의하자

 

자세한 풀이는 소스코드를 통해 알아보자

소스코드

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<int> oneDir(n + 1, 0);
    vector<bool> visited(n + 1, false);
    vector<int> vc[20001];
 
    for (int i = 0; i < edge.size(); i++) {
        //연결노드 정보를 토대로 각 노드별 인접노드 정보를 저장
        vc[edge[i][0]].push_back(edge[i][1]);
        vc[edge[i][1]].push_back(edge[i][0]);
    }
 
    queue<int> Queue;
    Queue.push(1);  //1번 노드에서 출발
    oneDir[1] = 0;
    visited[1] = true;
    int maxCnt = 0;
    while (!Queue.empty()) {
        int cur = Queue.front();    //현재 노드번호
        Queue.pop();
        int curDir = oneDir[cur];   //현재 노드에서 1번노드까지 가는 거리
 
        if (curDir > maxCnt) {    //현재노드에서 1번노드까지 가는 거리가 최대보다 큰 경우
            maxCnt = curDir;    //최대값 갱신
            answer = 1;         //counting 1로 초기화
        }
        else if (curDir == maxCnt) { //현재노드에서 1번노드까지 가는 거리가 최대와 같은 경우
            answer++;   //counting 1만큼 
        }
 
        for (int i = 0; i < vc[cur].size(); i++) {
            //인접논드 중 방문하지 않은 노드들 처리
            if (!visited[vc[cur][i]]) {
                Queue.push(vc[cur][i]);
                oneDir[vc[cur][i]] = curDir + 1;  //현재 노드에서 +1한 거리가 1까지 도달하는데 필요한 최단거리
                visited[vc[cur][i]] = true;
            }
        }
    }
 
    return answer;
}