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

https://www.acmicpc.net/problem/1389

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

 

 

- BFS

 

import sys
input = sys.stdin.readline

from collections import deque

class Graph:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0] * size for _ in range(size)]
        self.visited = [False] * size
        self.predecessor = [0] * size
    
    def addEdge(self, u, v):
        self.matrix[u][v] = self.matrix[v][u] = 1
    
    def bfs(self, start):
        q = deque([start])
        self.visited[start] = True
        while len(q) != 0:
            k = q.pop()
            for i in range(self.size):
                if self.matrix[k][i] == 1 and self.visited[i] == False:
                    q.appendleft(i)
                    self.visited[i] = True
                    self.predecessor[i] = self.predecessor[k] + 1

        return sum(self.predecessor)

    def resetList(self):
        self.visited = [False] * self.size
        self.predecessor = [0] * self.size

n, m = map(int, input().split())

g = Graph(n)
for _ in range(m):
    u, v = map(int, input().split())
    g.addEdge(u-1, v-1)

number = list()
for i in range(n):
    number.append(g.bfs(i))
    g.resetList()

print(number.index(min(number))+1)

 

BFS 최단 경로 문제이다~

 

채점 현황을 보면 Python 코드 중 유독 내 코드만 좀 긴 느낌이 난다ㅎ;;;

아마 class 사용하는 것도 있고, resetList를 따로 만들어서 그럴 수도 있겠다 싶었는데 굳이 로직에 문제는 없으니까 뭐..

 

알고리즘 분류에 플로이드-워셜 이라고 있던데, 음의 가중치를 가진 그래프에서 모든 최단 경로를 구하는 알고리즘이라고 한다

 

다익스트라는 양의 가중치만 되던데 얘는 음의 가중치도 된다고 하니까 신기했다 근데 아직 배울 생각은 없고.. 나중에 가중치 문제 나오게 되면 한 번 공부해볼 예정이다