파이썬으로 풀어보는 백준 2660번: 회장뽑기

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

2660번: 회장뽑기

 

내 풀이:

def check(i, j):
    queue = [i]
    checking = []
    cnt = 0
    table = [1]
    while queue:
        a = queue.pop(0)
        if field[a][j] == 1:
            break
        else:
            checking.append(a)
            for num, i in enumerate(field[a]):
                if i == 1 and num not in checking:
                    queue.append(num)
                    table.append(table[cnt]+1)
            cnt += 1
    return table[cnt]
 
N = int(input())
field = [[0] * (N+1) for _ in range(N+1)]
result = [[0] * (N+1) for _ in range(N+1)]
 
while True:
    a, b = map(int,input().split())
    if a == -1:
        break
    field[a][b] = 1
    field[b][a] = 1
 
 
score = [0] * (N+1)
score[0] = 100
 
for i in range(1, N+1):
    for j in range(1, N+1):
        if i == j or result [i][j] != 0:
            pass
        else:
            value = check(i, j)
            result[i][j] = value
            result[j][i] = value
for i in range(1, N+1):
    score[i] = max(result[i])
 
cut = min(score)
lst = []
for idx, i in enumerate(score):
    if i == cut:
        lst.append(idx)
 
print(cut, len(lst))
print(" ".join([str(i) for i in lst]))

 

newprog님의 풀이:

import sys
 
n = int(input())
a = [[0 for _ in range(n+1)] for _ in range(n+1)]
 
while True:
    t = list(map(int, sys.stdin.readline().split()))
    if t[0] == -1:
        break
    a[t[0]][t[1]] = 1
    a[t[1]][t[0]] = 1
 
def find(idx):
    s = {idx}
    q = [(idx, 0)]
    m = 0
    while len(q) != 0:
        p, d = q.pop(0)
        m = d
        for i, e in enumerate(a[p]):
            if e == 1 and i not in s:
                q.append((i, d+1))
                s.add(i)
    return m
 
score_dic = dict()
for i in range(1,n+1):
    score_dic[i] = find(i)
sort = sorted(score_dic.items(), key=lambda x: x[1])
count = n
can = ""
for i, e in enumerate(sort):
    if e[1] != sort[0][1]:
        count = i
        break
    else:
        can += str(e[0]) + " "
print(sort[0][1], count)
print(can.strip())

Python3, 56ms

 

앞서 언급한 깊이가 stack이라는 개념인 것 같다. 이에 관한 공부는 다음에 이어나갈 계획이다.