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

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

프로그래머스

 

 

 

이 문제는 처음에 DFS로 했다가 삽질하고 그냥 BFS로 한 것

어려워.. BFS, DFS 어려워ㅜㅜㅜㅜ

다행이 이 문제는 1부터라고 start를 딱 정하고 나머지는 신경안쓰고 최단거리라고 해서 distance[] == -1 로 간지 안간지 확인하고 그냥 이전꺼랑 dp처럼 더해서 다행이지..

 

난 왜케 생각 많이 했지? dp처럼 안된다고 생각함.

왜냐면 2-4, 5-4이 연결되어있으면, 1-2-5, 1-2-5-4 니까 뭐가 어디서 꼬일거다라고 생각했는데 그냥 어림도 없음

 

예시로 구체적으로 아래처럼 써보면서 생각해봐야지~

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

준거를

정리하면

1: 2, 3

2 : 1, 4, 5

3: 1, 2, 4

4: 2, 3

5: 2

6: 3

으로 된다. 

 

알아야할것 

1. BFS

- BFS에 deque랑 dictionary 들어감. 

- dictionary는 해당 노드와 연결된 노드 여러개를 저장을 위함

- deque는 내가 해당 노드를 작업 완료했으면 그 노드와 연결되어있는 노드를 저장하기 위함임 

- 기존에 갔던 것 체크 = distance 리스트로 

- 구성요소에 기본적으로 visit, deque, dic이 들어간다

 

2. deque

from collections import deque

check = deque()
check.append(1)

#위에 두줄이 아래와 같음
check = deque([1])

 

3. dictionary 

graph = {} #초기화

# 1부터 n까지의 key에 value는 []로 저장
for i in range(1, n+1):
        graph[i] = []
        
        
# 해당 key에 value 추가
for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])

 

4. count, max 함수

max_dis = max(distance)
    
answer = distance.count(max_dis)

 

 

 

 

정답

from collections import deque

def solution(n, edge):
    
    # dictionary로 매칭되는 점 하기
    graph = {}
    for i in range(1, n+1):
        graph[i] = []
    
    # key를 노드, value를 노드와 연결된 노드 번호
    for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
        
    # 길이를 매긴 것과 연결된 노드를 저장하는 것 = check
    check = deque([1])
    
    # 거리 저장
    distance = [-1] * (n+1)
    distance[1] = 0
    
    while check:
        current = check.popleft()
        
        for i in graph[current]:
            if distance[i] == -1:
                distance[i] = distance[current] +1
                check.append(i)
    
    max_dis = max(distance)
    
    answer = distance.count(max_dis)
    
    return answer