[Python/프로그래머스]가장 먼 노드_그래프(BFS)

 

 

 

 

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

코딩테스트 연습 - 가장 먼 노드

 

 

 

---

 

 

 

 

정말 사람의 기억력은 덧없다.

내가 BFS문제를 몇개를 풀었는데 

몇달 안풀었다고 또 잊어버렸다.

 

 

어쩔수 없지 계속 푸는 수 밖에 !!!!

 

 

 

---

1. 그래프 정보 수집

2. 덱을 만들어 시작 노드(1) 을 삽입

3. 덱이 빌 때까지 빼면서 방문하지 않은 노드를 방문하여 vis +1 

4. 가장 멀리 떨어진 노드 ( 가장 큰수)를 구해 count를 이용해 개수 return 

 

 

 

 

vis[1] = 1을 두고 덱에 1을 삽입해 놓는다. 

그리고 1 주변을 돌면서 안가본 것들을 현재 값 +1 을 하여 저장한다. 

그리고 다시 덱에 넣는다. 

 

 

 

 

코드 : 

from collections import deque
def solution(n, edge):
    mp = [[] for _ in range(n+1)]
    vis = [0] *(n+1)
    
    for a,b in edge :
        mp[a].append(b)
        mp[b].append(a)
    
    vis[1] = 1  # 1에서 시작 
    q = deque([1])
    
    while q : 
        now = q.popleft()
        for i in mp[now] :
            if vis[i] == 0 : #  첫방문
                vis[i] = vis[now] + 1 
                q.append(i)
                
    max_v = max(vis)
    answer = vis.count(max_v)
        
    return answer

 

 

 

배운 점 :

 

1. count 

list안에 있는 특정 수의 개수를 구하고 싶을 때 count를 쓴다. 

[리스트 이름].count( [개수를 알고싶은 숫자 ] )

 

 

 

참고 블로그 : 

 

 

 

https://whwl.tistory.com/268

[프로그래머스] 가장 먼 노드 / 파이썬 / python / BFS

 

 

복습 : 

✅ 20220619

✅ 20220621

✅ 20220622

✅ 20220623

✅ 20220624

✅  20220625

✅ 20220626

✅ 20220630

✅ 20220701

✅ 20220702