[백준] [파이썬] [Graph] [BFS] 2660번: 회장뽑기 (플로이드-워샬 응용)

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

문제 보러 가기

2660번: 회장뽑기

 

 

 

유사한 문제 -> 1389번: 케빈 베이컨의 6단계 법칙

유사한 문제 -> 11404번: 플로이드 

문제

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 붙어 있다. 마지막 줄에는 -1이 두 개 들어있다.

출력

첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고, 두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

예제 입력 1

5
1 2
2 3
3 4
4 5
2 4
5 3
-1 -1

예제 출력 1

2 3
2 3 4

---

 

내가 도달 할 수 있는 가장 끝 노드까지 관계 길이라고 생각하면 편하다.

관계의 길이가 가장 긴게 그사람의 점수가 된다.

즉, 시작할때 1을 갖고 한사람 관계당 +1이 된다. 

 

친구관계를 다음과 같다.

1: [2]

2: [1,3,4]

3: [2,4,5]

4: [3,5,2]

5: [4,3] 

 

1번 노드부터 진행하면 큐에 1을 넣고 1번은 2번 친구가 있다. 

[0,1,2,0,0,0]이 되고 큐에 [2]가 들어간다. (1+1=2)

2번 노드로 넘어가면 2번은 1,3,4번 친구가 있고 1번은 이미 방문한적이 있으므로

[0,1,2,3,3,0]이 되고 큐에 [3,4]가 있게 된다. (2+1=3)

3번 노드로 넘어가면 3번은 2,4,5번 친구가 있고 중복을 제외하면 

[0,1,2,3,3,4] 가 되고 큐에 [4,5]가 있게 된다. (3+1=4)

4번 노드로 넘어가면 4번은 3,5,2번 친구가 있고 중복을 제외하면 

그냥 큐의 5번 노드로 넘어간다.

5번 노드로 넘어가면 5번은 4,3번 친구가 있고 중복을 제외하면 

변하는거는 없다. 

그럼 최종 visited는 [0,1,2,3,3,4]이고 info는 [0,4,0,0,0,0]이다. max 값은 4로,

1번은 친구의 친구의 친구(3+1)가 있는 사람이다. 

 

나머지 번호도 반복하면 info는 [0,4,3,3,3,4]이다. 

가장 작은 점수, 가장 관계가 가까운 후보자는 3값의 score를 갖는 2,3,4번 사람이다.

 

최종적으로 3-1=2가 회장 후보의 점수, 후보자 2,3,4번 사람들 수인 3이 후보의 수.

두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

 

---

BFS로 푼 코드

import sys 
from collections import deque 

sys.stdin=open("input.txt",'r')


if __name__=="__main__":
    N=int(input())                          # 회원의 수 
    graph=[[] for _ in range(N+1)]
    while True:
        u,v=map(int,input().split())
        if u==-1 and v==-1:
            break 
        graph[u].append(v)
        graph[v].append(u)

    info=[0]*(N+1)
    scroe=sys.maxsize

    for i in range(1,N+1):              # 1번 회원부터 N번 회원까지 
        visited=[0]*(N+1)
        Q=deque()
        Q.append(i)
        visited[i]=1

        while Q:
            x=Q.popleft()
            for k in graph[x]:          # x의 친구들 
                if visited[k]==0:       # 재방문 확인 
                    visited[k]=visited[x]+1 # 친구관계당 +1이 됨
                    Q.append(k)
        info[i]=max(visited)    # 친구의 친구의... 관계가 가장 먼거 
        if scroe>info[i]:
            scroe=info[i]       # 최저 점수

    candidates=[]
    for i in range(1,N+1):
        if info[i]==scroe:      # 최저 점수를 갖는 사람이 후보 
            candidates.append(i)

    print(scroe-1, len(candidates)) # 최저점수와 후보자수 출력 
    print(*candidates)              # 후보자 번호 출력

 

---

플로이드-워샬 방법

 

이 방법을 꼭 기억하자 이게 더 좋아보인다.

 

노드와 간선을 2차원 배열로 나타내자.

---

import sys 
sys.stdin=open('input.txt','r')

if __name__=="__main__":
    n=int(input())
    dis=[[100]*(n+1)for _ in range(n+1)]
    for i in range(1,n+1):      # 자기자신은 0이다. 대각선은 0으로 초기화
        dis[i][i]=0
    
    while True:
        a,b=map(int, input().split())
        if a==-1 and b==-1:             # 가장 마지막 -1,-1이면 그만 
            break
        dis[a][b]=1
        dis[b][a]=1
    # ------------- 입력 끝 ---------------
    
    for k in range(1,n+1):          # 중간에 거치는 가능 한 노드를 다 봄
        for i in range(1,n+1):      # i->j
            for j in range(1,n+1):
                dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j])

    # ------------ 관계도 그리기가 완전 끝남 --------------------------
    
    res=[0]*(n+1)
    score=100
    for i in range(1,n+1):
        for j in range(1,n+1):
            res[i]=max(res[i], dis[i][j])       # 각 i번 회원에 최대값 
        score=min(score, res[i])                # 가장 적은 값을 갖는 사람이 회장이기 때문에 가장 적은값을 구한다.
        
    out=[]
    for i in range(1,n+1):
        if res[i]==score:
            out.append(i)
    print("%d %d" %(score,len(out)))
    print(*out)

---