글 읽기 - 왜 틀린 건지 잘 이해가 가질 않아요

csw9595 3년 전 0

노드들을 c1은 작게 c2는 크게해서 1 -> 큰 수로 찾을 수 있게끔 edges에 저장했습니다.

이후에 infected는 1로 시작해서 1에 연결된 노드들을 추가, 그 후 추가된 노드들로부터 다시 또 비교하는 식으로 알고리즘을 구현했습니다.

예제도 잘 수행이 되는데 어떤 점을 간과했는지 잘 모르겠습니다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

edges = []
for _ in range(m):
    c1, c2 = map(int, input().split())
    if c1 > c2:
        edges.append((c2, c1))
    else:
        edges.append((c1, c2))

infected = [1]

for node in infected:
    for i in range(node+1, n+1):
        if (node, i) in edges:
            infected.append(i)
print(len(infected) - 1)

sonjaewon 3년 전 0

dfs/bfs 사용하는 문제인데 그렇게 보이지가 않네요.

pmn0001 3년 전 0

1 2

2 4

3 4

result : 2

ans : 3

반례입니다.

또 중복으로 infected 에 원소를 넣지는 않는지요?

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

문제

문제

출처

ICPC

왜 틀린 건지 잘 이해가 가질 않아요

csw9595 3년 전 0

sonjaewon 3년 전 0

pmn0001 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말