[프로그래머스 lv 3] 가장 먼 노드.py

<문제 설명>

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

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

n개의 노드가 있는 그래프가 있다. 각 노드는 1번 부터 n번 까지 번호가 부여되어 있다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하면 되는 문제이다.

이때 가장 멀리 떨어지는 노드는 최단 경로로 해당 노드까지 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다.

 

입출력의 예는 다음과 같다.

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

예시의 그래프를 표현한 이미지

 

<문제 풀이 아이디어>

우선 방문한 노드를 저장할 1차원 배열과, 입력에 따라서 그래프를 표현할 공간을 이차원 배열로 만든다. 이후 반복문으로 각 노드에 대한 연결 정보를 저장한다. 이후에는 DFS로 방문한 노드와 각 노드 별 1번 노드 부터의 거리를 계산한다.

이 계산한 거리들 중 제일 긴 거리를 추출하고, 이 거리를 가진 노드가 몇 개 있는지 카운트해서 리턴한다.

 

<문제 풀이 코드>

from collections import deque

def bfs(v, visited, adj):
    cnt = 0
    q = deque([[v,cnt]]) #노드별 카운트를 같이 저장
    while q:
        value = q.popleft()
        v = value[0] #노드
        cnt = value[1] #카운트
        if visited[v] == -1: #방문 안했으면
            visited[v] = cnt #카운트 저장
            cnt += 1 #다음 깊이?로 가야 해서 증가
            for e in adj[v]:
                q.append([e,cnt]) #다음 탐색할 것 큐에 저장

def solution(n, edge):
    answer = 0
    visited = [-1] * (n+1)
    adj = [[] for _ in range(n+1)]
    #공간 만들어서 입력에 따라 그래프를 표현해줌
    for e in edge:
        x = e[0]
        y = e[1]
        adj[x].append(y)
        adj[y].append(x)
    
    bfs(1,visited,adj)
    for value in visited:
        if value == max(visited):
            answer += 1
    return answer

채점 결과