1389번, 1697번

1. 케빈 베이컨의 6단계 법칙

링크 - https://www.acmicpc.net/problem/1389

코드

import sys
input = sys.stdin.readline
#무한대
INF = int(1e7)
#노드, 간선
n,m = map(int,input().split())

graph=[[INF]*(n+1) for i in range(n+1)]

#자기 자신은 0으로 초기화
for i in range(1,n+1):
    for j in range(1,n+1):
        if j==i:
            graph[i][j]=0
        
#친구 입력 받기
for _ in range(m):
    a,b = map(int,input().split())
    graph[a][b]=1
    graph[b][a]=1 #둘은 칭구칭긔

#플로이드 워셜 실행
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])

#케빈베이컨수 구하기
min_kb =sum(graph[1][1:])
idx=1
for i in range(2,n+1):
    kb = sum(graph[i][1:])
    if min_kb>kb:
        min_kb= kb
        idx = i
print(idx)

친구를 노드라고 할 때,
모든 노드에서 모든 노드의 경로를 파악해야 하기 때문에 플로이드 워셜로 풀었다.

• 간선의 개수 m만큼 입력을 받아야 하는데 n이라고 적어서 계속 틀렸었다. OTL ㄱ-

2. 숨바꼭질

링크 - https://www.acmicpc.net/problem/1697

코드

import sys
from collections import deque

#input= sys.stdin.readline

def bfs(start,end):
    q = deque()
    count=0
    q.append([start,0])
    visited = [False]*(100001)
    visited[start]=True
    
    while q:
        num,count = q.popleft()
        if num==end:
            return count
        for i in [num+1, num-1,num*2]:
            if 0<=i<=10**5:
                if visited[i]==False:
                    q.append([i,count+1])
                    visited[i]=True
    
s, d= map(int,input().split())

print(bfs(s,d))

처음에는 dfs로 문제를 풀려고 했는데 종료조건을 못잡아주겠어서 bfs로 바꿨다.
계속 런타임 오류가 났는데 알고보니 visited리스트의 크기를 잘못적어줘서 오류가 생긴거였다. 하하하 즐겁다