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

문제

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

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스

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

 

 

알고리즘

def my_sol(n, edges):
    graph = [[] for i in range(n+1)]

    for i in range(len(edges)):
        if edges[i][1] not in graph[i]:
            graph[edges[i][0]].append(edges[i][1])

        if edges[i][0] not in graph[i]:
            graph[edges[i][1]].append(edges[i][0])

    print("Graph: ", graph, "\n")



    """
    이 위로는 데이터 준비 과정
    이 밑으로는 너비 우선 탐색을 통해 dist 배열에 값 채워넣는 과정
    """
    
    start = 1
    queue = [start]
    dist = [0] * (n+1)
    dist[0] = -1
    dist[start] = -1
    count = 1

    # 1번 노드와 다른 노드와의 거리에 대한 값을 갖는 dist 배열에 0이 없을 때까지 반복한다.
    # 이는 1과 연결된 모든 노드를 방문한다는 뜻이다.
    while 0 in dist:
        # new_arr 배열은 다음 단계에 탐색할 노드들을 저장하기 위한 배열이다.
        new_arr = []

        # queue에 담겨 있는 노드들마다 bfs를 한다. 즉, 시작 노드에서 갈 수 있는 노드들을 방문한다.
        # 처음 반복을 시작할 때는 [1]이므로, start는 1이다.
        print("시작하는 큐: ", queue)
        for start in queue:
            print("탐색을 시작하는 노드: ", start)

            # start에서 갈 수 있는 노드들을 탐색한다. start가 1인 경우, cand는 3, 2 이다.
            for cand in graph[start]:
                
                # dist[cand]는 1번 노드와의 거리를 나타낸다. 이 값이 0이라면, 아직 방문되지 않은 것이다.
                # 따라서, dist[cand]의 값을 count만큼 증가시키고, new_arr 배열에 append한다.
                if dist[cand] == 0:
                    print("bfs로 탐색한 노드: ", cand)
                    dist[cand] += count
                    new_arr.append(cand)
        print("새로 만들어진 큐: ", new_arr, "\n")
        count += 1
        queue = new_arr

    print("dist: ", dist, "\n")
    return dist.count(max(dist))


edges = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
n = 6
print("정답: ", my_sol(n, edges))

 

설명

그래프란, 정점(node 또는 vertex)과 간선(link 또는 edge)으로 이루어진 자료구조를 말한다. 정점을 학생1, 학생2, ... , 학생n이라고 한다면, 간선은 학생a와 학생b 사이에 유의미한 관계(사귄적이 있다거나, 채무관계가 있다거나)가 있음을 나타낸다. 

이 문제를 풀기 위해서, BFS(너비 우선 탐색)을 활용하였다. 주어진 edge에 대한 정보를 바탕으로, 딕셔너리와 비슷하게 생긴 배열을 만든다. 아래에 Graph를 보면, 

index	0	1	2	3	4	5	6
값	[]	[3, 2]	[3, 1, 4, 5]	[6, 4, 2, 1]	[3,2]	[2]	[3]

이렇게 구성되는 것을 볼 수 있다. 

dist 배열은 아래와 같다. 

index	0	1	2	3	4	5	6
값	-1	-1	0	0	0	0	0

0은 문제에서 사용하지 않으므로, 그 값에 -1을 넣었다. 그리고 1번 노드는 출발점이므로 정답이 될 수 없으므로 -1을 넣었다. 나머지 인덱스에는 0을 넣었다. 

시작점은 1이므로, start = 1 이고, queue = [start] 를 선언한다. 

그리고 count변수를 선언하고 1로 초기화한다. count는 bfs가 한번 진행될 때마다 1씩 증가한다. 이 변수를 이용해서, 1에서 1번의 bfs로 갈수 있는 노드 i가 있을 경우 dist[i] += count (= 1), 2번의 bfs로 갈 수 있는 노드 i가 있을 경우
dist[i] += count(= 2) 이런 식으로 각 노드가 1번 노드에서 출발해서 몇 번만에 갈 수 있는지 파악할 것이다. 

1. dist 배열에 0이 없을 때까지 반복한다. ( = 1과 연결된 모든 노드를 방문할 때까지 반복한다.)
   1. queue에 있는 노드들을 for문을 통해 순회한다. 이 노드를 start라 칭하겠다.
      1. start노드에서 갈 수 있는 노드들을 순회한다. 이 노드를 cand(candidate에서 따옴 ㅎㅎ)라 칭하겠다.
         1. dist[cand]의 값이 0이라면, 이 노드는 아직 방문되지 않은 노드이다. 따라서, dist[cand]의 값을 count만큼 증가시킨다.
            그리고, new_arr 배열에 append한다. 왜냐하면 다음 반복에서 탐색을 시작하는데 사용할 노드이기 때문이다. 
   2. count를 1 증가시킨다.
   3. queue 에 new_arr을 할당한다. 
2. 각 노드까지의 거리를 담고 있는 dist배열의 최대값을 count해서 리턴한다. 

결과

올바른 결과를 출력한다. 

가장 위의 Graph는 문제 해결을 위해 딕셔너리와 비슷한 리스트를 만든 것이다. 그리고, bfs의 각 반복이 어떻게 흘러가는지를 print문을 통해 콘솔창에 나타내었다. 

후기

너모너모 어려웠다. 네트워크 문제를 푼 이후 좀 더 심화된 DFS/BFS는 푸는게 너무 힘들다. 반복 숙달 훈련이 필요한 것같다. 구분 동작을 통해 배워보는것이 선행되어야 한다. 

그리고, 제한사항을 보면 알겠지만 노드의 갯수가 2 ~ 20000개이다. 처음에는 이 점을 간과하고 인접행렬을 만들어서 풀었는데, 효율성에서 다 떨어지더라. 2차원 배열을 만들면 데이터가 너무 커지고 그에 따라 시간 복잡도도 올라간다. 따라서, 이 문제는 무조건 인접 리스트 형태로 데이터를 만들어서 풀어야 한다. 

DFS BFS를 활용함에 있어서, 너무 틀에 박힌 활용만 하는 것 같다. 네트워크 문제를 예로 들면, 거기선 BFS든 DFS든 뭘 기록할 필요가 없었다. 

while queue:
	start = queue.pop(0)
    
    for i in range(len(graph[start])):
    	if graph[start][i] not in visited:
        	visited.append(i)
            queue.append(i)

이런 식으로, 방문한 노드는 바로바로 버리면서 방문하지 않은 모든 노드에 대해 탐색을 할 수 있었다. 근데 좀 있다 업로드 할 여행 경로 문제를 보면, 한 노드를 여러 번 반복할 수도 있고, 어느 경로가 조건에 맞지 않는다면 그 경로를 버리고 다시 돌아가야하는데, 이런 응용이 들어가니까 얼추 개념을 알아도 구현을 하나도 못하겠더라. 문제가 복잡하고, 어떤 정보를 기록해야 한다면 pop보다는 for문을 이용해서 탐색할 노드를 고르는 것이 중요한 것 같다. 너무 어렵당 ㅋ