💡 문제 해결 아이디어

🛠 피드백

• 깜빡한 사실 : 그래프를 주어진 그대로 두는 것보다, Adjacency List나 Adjacency Matrix로 표현하는 것이 일반적이고, 효율적이다
• 따라서 dictionary 그 중에서도 defaultdict라는 것을 이용해 Adjacency List를 구현했다.
• 이후에, BFS를 통해서 연결된 모든 Node의 distance를 측정했다.
• 모든 edge의 길이가 동일하고, queue를 통한 BFS이므로 나중에 방문한 경우가 최단경로일 수가 없다.

내가 생각한 아이디어

• deque를 이용해서 queue를 구현하고, 주어진 edge들을 for문으로 반복하면서 인접한 노드들을 방문하는 BFS를 통해 풀어보자!

💻 작성된 코드(수정)

from collections import deque, defaultdict

def solution(n, edge):
	# 거리 저장용이면서, 방문 여부 확인용
    distance = [0] * (n+1)
    # 해당 key가 없는 경우 지정해준 자료형으로 자동 생성 시켜준다.
    # 그냥 dict로 해도 되지만, 해당 key가 없는 경우를 별도로 처리해줘야한다.
    vertex = defaultdict(list)
    
    # 주어진 edge들을 통해 dictionary 형태로 Adjacency List 구현
    for e in edge:
        vertex[e[0]].append(e[1])
        vertex[e[1]].append(e[0])
    
    # 본격적인 BFS 시작
    queue = deque()
    queue.append(1)
    
    # queue가 차있는 동안 (1번 Node가 포함된 conected component에 대해)
    while queue:
        recent = queue.popleft()
        dist = distance[recent]
        # 인접한 노드들 중에서
        for neighbor in vertex[recent]:
        	# 1번 Node가 아닌데, 방문한 적이 없으면,
            if neighbor != 1 and distance[neighbor] == 0:
            	# queue에 추가해주고, 최근거리+1을 저장 (방문처리)
                queue.append(neighbor)
                distance[neighbor] = dist + 1
    # 가장 먼 거리의 Node 개수를 count해서 return
    return distance.count(max(distance))