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

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

프로그래머스

그래프 Graph

 

 

이런식의 그래프가 주어집니다. 간선에 붙은 가중치는 없구요. 양방향 간선이고, [점1, 점2] 을 요소로 갖는 배열이 하나 주어짐. 노드는 n개, 노드 번호는 1~n. 이때, 1로 부터 최단 경로가 가장 먼 노드는 몇개인가.

즉, 1을 제외한 모든 노드에 대해 1부터 해당 노드까지 도달하는 최단 경로를 구하고, 그 중 가장 먼 거리에 있는 노드는 몇개인지 묻는 문제.

즉, (ㅇㄴ) 최단 경로 중에 최댓값을 뽑고, 이 최댓값이랑 거리가 같은 노드가 몇개인지 세면 된다

 

 

 

 

 

 

접근방법

방금 말했네요..모든 노드에 대해 1로부터의 최단 거리를 구해놓고, 그 중 최댓값을 찾은 후에, 다시 그 최댓값과 같은 최단 거리를 같은 노드는 몇개인지 구했다. (마지막 두개가 굉장히 비효율적이라고는 생각합니다..)

최단 거리를 구하는 것은, 우선 인접행렬을 사용했구요 (각 노드에 대해 직접적으로 연결된 노드를 저장해둔 2차원 배열), 1부터 본인까지의 최단거리를 저장해두는 1차원 배열 distance를 사용함. 1부터 시작해서 bfs처럼 연결된 노드를 하나씩 방문해가면서 최단거리를 갱신하면 됩니다. (이미 방문한 곳은 또 방문하지 않음. 여기서, 방문했다 = 나로부터 갈 수 있는 모든 노드를 체크했다 (혹은 큐에 담았다) 그래서 visit bool 배열도 필요함)

진짜 불친절한 설명이다

갱신하는 조건은 지금 방문한 노드(지금 큐에서 뺀 노드)를 now라고 하고, now로부터 갈 수 있는 노드를 dest 라고 할 때,

dest의 현재 최단 거리 vs (1에서부터) now까지의 최단거리 + 1(지금 보고있는 간선 = now~dest) 이 둘을 비교해서 적은걸 dest의 최단거리로 저장한다.

 

그러면 1로부터 갈 수 있는 모든 노드를 방문하게 되고, 그러고나면 distance배열에는 1에서부터 본인 노드에 이르기까지의 최단거리가 저장된다. 이때 이중 최댓값을 저장하고, 또 distance배열을 순회하면서 최댓값과 같은 경우를 count하면 된다.

 

끝

 

오답노트

처음에 visit를 체크를 안해서 틀렸었음..

(하루 뒤에 쓰면 이게 안좋네요. 오답노트 쓸 게 생각이 안남..)

지금 다른 사람 풀이 보고왔는데, 최댓값을 while문 안에서 갱신하면 (즉, distance배열에 변화가 생길 때 갱신해주면) 되네요

 

소스코드

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int max = 0;
    
    int m = edge.size();
    vector<int> distance(n+1, 50001);
    vector<bool> visit(n+1, false);
    
    // 인접행렬 만들기
    vector<vector<int>> adj(n+1);
    for(int i = 0 ; i < m ; i++){
        adj[edge[i][0]].push_back(edge[i][1]);
        adj[edge[i][1]].push_back(edge[i][0]);
    }
    
    // q에 1번노드 넣기 (출발점이라 처음에 방문)
    queue<int> q;
    q.push(1);
    distance[1] = 0;
    
    // 각 노드의 최단 경로 구하기 (BFS)
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        for(int i = 0 ; i < adj[now].size() && !visit[now] ; i++){
            int dest = adj[now][i];
            if(distance[dest] > distance[now] + 1){
                distance[dest] = distance[now] + 1;
                // 최댓값 구하기
                if(max < distance[dest]){
                    max = distance[dest];
                }
            }
            q.push(dest);
        }
        visit[now] = true;
    }
    
    // 최댓값인 경로 갯수
    for(int i = 1 ; i <= n ; i++){
        if(max == distance[i]){
            answer++;
        }
    }
    
    return answer;
}

 

 

 

 

 

티스토리도 블챌 한답니다~ 어차피 문풀 매일해야되는데 오히려 좋아..~

동기가 두개잖아 러키비키 블챌비키잖아

https://www.tistory.com/event/write-challenge-2024

작심삼주 오블완 챌린지