프로그래머스 코딩테스트 연습 Level 3 - 가장 먼 노드 (Python)

프로그래머스 코딩테스트 연습 Level 3 - 가장 먼 노드 (Python)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 3 중 그래프, 너비 우선 탐색(BFS) 관련 문제인,

[가장 먼 노드] 문제를 Python를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

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

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

 

제한사항

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

 

입출력 예

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

 

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

 

작성한 답

solution.py

def solution(n, edge):
    adj = [[] for _ in range(n + 1)]
    for v1, v2 in edge:
        adj[v1].append(v2)
        adj[v2].append(v1)
    
    ch = [0 for _ in range(n + 1)]
    ch[1] = 1
    
    queue = [1]
    
    while queue:
        cur = queue.pop(0)
        for dest in adj[cur]:
            if not ch[dest]:
                ch[dest] = ch[cur] + 1
                queue.append(dest)
        
    return ch.count(max(ch))

 

설명

BFS를 사용하여 간단히 문제를 해결할 수 있습니다!

 

먼저 edge 배열에 들어있는 서로 연결된 노드들을 반복문을 돌면서 adj 라는 인접 노드들을 담아둘 배열에 각 Index 별 인접 노드를 배열로 담아둡니다.

예시의 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 배열이 edge로 주어진다면,

adj는 [[], [3, 2], [3, 1, 4, 5], [6, 4, 2, 1], [3, 2], [2], [3]] 이렇게 됩니다.

각 Index에 해당하는 노드와 연결된 노드들이 몇번 노드인지 쉽게 확인하고 반복문을 돌 수 있기 위해 이렇게 해줍니다.

 

그리고 이제 BFS를 사용하기 위해 이미 방문한 노드라는 것을 체크해둘 변수를 노드들의 개수보다 1개 많은 크기의 배열로 모든 값을 0으로 초기화해줍니다. (1개 많게 하는 이유는 만약 3번 노드라면 index 2가 아닌 index 3으로 사용함으로서 0부터 시작하는 배열을 사용하기 쉽도록 하기 위해서입니다.)

그리고 1번 노드에서 시작하므로 1번 노드는 1로 만들어줍니다. 또한 이 ch 배열은 그저 방문했다는 것만 체크하는 용도가 아닌 해당 Index의 노드가 1번 노드에서 몇칸이나 떨어져있는지 같이 담아줄 용도로 사용하게 됩니다.

 

이제 BFS를 사용하기 위한 queue 배열을 하나 만들고 1부터 시작하기 때문에 1을 미리 넣어둡니다.

이제 1 부터 시작해서 미리 만들어둔 adj 배열에서 현재 노드의 인접 노드들을 반복문을 돌며 이미 방문하지 않은 노드라면 현재 노드의 방문 여부를 ch 배열에 넣어주는데 현재 노드 Index에 해당하는 ch의 값은 1 번 노드에서 얼마나 떨어져 있는지를 담고있을테니 그 값에 1을 추가하여 넣어줍니다.

단, 1번 노드가 1의 값을 가지므로 1번 노드와 떨어진 거리 + 1 의 값을 가지게 될겁니다. 하지만 가장 멀리 있는 노드의 개수만 구하면 되는 문제이니 문제가 되지 않습니다.

 

위 과정을 모두 반복하면 ch 배열에는 각 노드가 1번 노드와 얼마나 떨어져있는지 값을 볼 수 있습니다.

위 예제에서는 [0, 1, 2, 2, 3, 3, 3] 와 같은 값을 가지게 될것입니다.

위 예제의 값에서도 볼 수 있듯이 각 숫자는 [1번 노드와 떨어진 거리 + 1] 의 값을 가지고 있으며 앞서 말씀드렸듯이 1이 더 큰 값을 가져도 상관없습니다. 문제는 가장 멀리 있는 노드의 개수만 구하면 되는 것이기 때문입니다.

 

그럼 이제 ch 배열에서 가장 큰 값이 무엇인지 max()를 사용해서 찾을 다음, ch 배열에서 그 가장 큰 값을 가지는 요소가 몇개인지를 구하여 반환하는 것으로 문제를 해결할 수 있습니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.