[백준] python 파이썬 - 케빈 베이컨의 6단계 법칙

1389번: 케빈 베이컨의 6단계 법칙 (acmicpc.net)

1389번: 케빈 베이컨의 6단계 법칙

백준 1389번 : 케빈 베이컨의 6단계 법칙

 

 

처음 코드

# -*- coding: utf-8 -*-
import sys
from collections import deque

n, m = map(int ,input().split())
li = [[]for _ in range(n+1)]
visited = [False] * (n+1)
 
#인접리스트 구현
for _ in range(m) :
    i, j = map(int, input().split())
    li[i].append(j)
    li[j].append(i)

def bfs(num) :
    queue.append(num)
    visited[num] = True
    
    while queue :
       f = queue.popleft()
        
       for v in li[f] :
           if not visited[v] :
                visited[v] = visited[f] + True
                queue.append(v)
                # visit
    return sum(visited)
        
queue = deque()        
res = []
for i in range(1, n+1) :
    res.append(bfs(i))
    
print(res)

 

 

최종 코드

# -*- coding: utf-8 -*-
import sys
from collections import deque

n, m = map(int ,input().split())
li = [[]for _ in range(n+1)]
# visited = [False] * (n+1)
 
#인접리스트 구현
for _ in range(m) :
    i, j = map(int, input().split())
    li[i].append(j)
    li[j].append(i)

def bfs(num) :
    visited = [False] * (n+1)
    queue.append(num)
    visited[num] = True
    
    while queue :
       f = queue.popleft()
        
       for v in li[f] :
           if not visited[v] :
                visited[v] = visited[f] + True
                queue.append(v)
    return sum(visited)
        
queue = deque()        
res = []
for i in range(1, n+1) :
    res.append(bfs(i))
    
print(res.index(min(res))+1)

 

일단 최단거리를 구하는 거랑 비슷한 문제니까 BFS로 문제 풀어야 되겠다고 생각했고

둘의 차이가 무엇인지 느껴즈십니까?.. 바로바로 visited를 어디다 선언하느냐입니다.. 

아직도 뭐가 다른지 모르겠다. 오만거 다 바꿔보다가 저거 바꾸니까 갑자기 되길래.... 되는구나 함

   (+ 수정 : 당연하다!!!! li는 이차원 배열이기 때문에, 한 행에 따라서 visited를 생성해주는 거기 때문에 당연히 안에다가 생성해야 됨. 생각이 없네.. ) 

 

그거말고는 생각없이 걍 인접리스트 선언해서 BFS 사용했더니 됨. 아~~무 생각없이...

기묘하고 어렵고..