글 읽기 - 반례가 뭘까요? 63%쯤에서 오답이네요 ㅠㅠ

nakalic 1년 전 0

그래프 BFS 돌려서 회장점수 구하고

가장 낮은 값 구해서 출력하는데 63%쯤 넘어서 틀렸다고하는데 반례 있을까요 ?...

import sys
from collections import deque

input = sys.stdin.readline

N = int(input().strip())

adj = [[] for _ in range(N + 1)]
score = [float("inf")] * (N + 1)


def bfs(n):
    vis = [0] * (N + 1)
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        for j in adj[x]:
            if not vis[j]:
                vis[j] = vis[x] + 1
                queue.append(j)
    score[n] = max(vis)


while True:
    a, b = map(int, input().split())
    if a == b == -1:
        break
    adj[a].append(b)
    adj[b].append(a)

for i in range(1, N + 1):
    bfs(i)

ans = min(score)

print(ans, score.count(ans))
for i in range(1, N + 1):
    if score[i] == ans:
        print(i, end=' ')

amico741 1년 전 0

부분에서 bfs(n) n 매개 변수는 방문기록이 남아 있지 않기 때문에 vis[j] = vis[x] + 1로 더해질 수 있기 때문에
max(vis)에서 n의 인덱스는 제외하고 최대값을 구해야 합니다.

fksk94 6달 전 0

자신의 최소값은 빼고 계산해야합니다.

예를 들면 i -> i 로 가는 수는 무조건 최소 값이 2입니다. 왜냐하면 아는 친구한테 나 아냐고 물어보면 2니까요.

근데 vis 로 최대값을 구하시자나요. 다른 친구한테 도달하는 값들이 1이고 나한테 도달하는 값이 2가 된다면 맥스 값은 2가 되서 틀리는 겁니다.

p.s. 다른 플로이드 와샬 방법도 똑같이 자기자신으로 가는 수는 초기화 해주어야합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 뭘까요? 63%쯤에서 오답이네요 ㅠㅠ

nakalic 1년 전 0

amico741 1년 전 0

fksk94 6달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말