파이썬(Python) 알고리즘 문제풀이 베스트앨범 [프로그래머스 / Hash]

출처) 프로그래머스 Facebook

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

1. 노드의 개수 n은 2 이상 20,000 이하입니다.
2. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
3. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

 

 

입출력 예

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

 

 

풀이 코드

BFS 를 활용한 기본적인 가중치 그래프 문제.

양방향 그래프를 defaultdict 으로 만들고 BFS 를 활용해 다음 노드를 쭉쭉 탐색하는 방법을 안다면 어렵지 않게 풀이 할 수 있다.

먼저 그래프를 생성한다.

from collections import defaultdict

def solution(n, vertex):
    answer = 0
	graph = defaultdict(list)
    
    # 양방향 그래프 생성
    for a, b in vertex:
    	graph[a].append(b)
        graph[b].append(a)

 

 

 

그래프를 생성했다면 BFS 탐색을 위해 기본적인 세팅을 해주자. 1번 노드부터 시작한다고 했으니까 (1번 노드, 가중치 0) 를 Queue 에 넣어두고 1번 노드를 방문 처리한다. 이후 BFS 탐색을 하면서 count(가중치) 를 하나씩 증가시켜서 Queue 에 넣어준다.

from collections import defaultdict
from collections import deque

def solution(n, vertex):
    answer = 0
	graph = defaultdict(list)
    
    # 양방향 그래프 생성
    for a, b in vertex:
    	graph[a].append(b)
        graph[b].append(a)
        
   	queue = deque()
    queue.append((1, 0))
    
    visited = [False for _ in range(n + 1)]
    visited[1] = True
    
	while queue:
    	cur_node, count = queue.popleft()
        
		for next_node in graph[cur_node]:
        	if not in visited[next_node]:
            	visited[next_node] = True
                queue.append((next_node, count + 1))

 

 

문제에서 요구한대로 1번 노드와 가장 먼 노드 즉, 가중치가 가장 큰 노드 개수를 반환해야하니까 가중치를 기록하는 리스트를 하나 만들어준다. 이 리스트의 인덱스는 노드의 번호와 일치하게 만들어주자. while 반복문을 빠져나오면서 가중치 리스트에는 각 인덱스(=노드 번호) 의 가중치가 저장됐고, 최대 가중치보다 크거나 같은 가중치를 가진 인덱스(=노드 번호) 개수 만큼 answer 개수를 증가시킨다. 최종 코드는 아래와 같다.

from collections import defaultdict
from collections import deque

def solution(n, vertex):
    answer = 0
	graph = defaultdict(list)
    
    # 양방향 그래프 생성
    for a, b in vertex:
    	graph[a].append(b)
        graph[b].append(a)
        
   	queue = deque()
    queue.append((1, 0))
    
    visited = [False for _ in range(n + 1)]
    visited[1] = True
    
    node_dis = [0 for _ in range(n + 1)]
    
	while queue:
    	cur_node, count = queue.popleft()
        
		for next_node in graph[cur_node]:
        	if not in visited[next_node]:
            	visited[next_node] = True
                
                # 가중치 리스트에 기록 추가
                node_dis[next_node] = count + 1
                
                queue.append((next_node, count + 1))
                
    max_count = max(node_dis)
    for i in range(len(node_dis)):
    	if max_count <= node_dis[i]:
        	answer += 1
            
	return answer