글 읽기 - 파이썬 반례나 틀린 부분 요청드립니다.

tong39 2년 전 0

안녕하세요.
2주동안 맞왜틀을 외치다가 도저히 혼자 힘으로 해결이 안될 것 같아서 질문을 올립니다.

알고리즘 분류는 플로이드-와샬 ,깊이 우선 탐색, 그래프 탐색이지만
BFS + 완전탐색의 방법으로 해결하려고 했습니다.

예제출력은 맞지만 제출하니 '틀렸습니다'가 나오는 상황입니다.

제출 번호는 https://www.acmicpc.net/source... 입니다.

혹시 반례나 잘못된 부분이 어디인지 알 수 있을까요?

읽어주셔서 감사합니다.

import sys
from collections import deque
N,M = map(int,sys.stdin.readline().split())
beads = [[[],[]]for i in range(N+1)] # heavy와 light를 나눌 3차원 배열 생성
qu = deque()
for i in range(M):    #가벼운것을 0번 배열에, 무거운 것을 1번 배열에 각각 추가
    hev,lig = map(int,sys.stdin.readline().split())
    beads[hev][0].append(lig)
    beads[lig][1].append(hev)

ans = 0
for i in beads:
    for j in i[0]:		# 가벼운 것 먼저 bfs로 돌면서 완전탐색
        qu.append(j)
    while qu:
        x = qu.popleft()
        for k in beads[x][0]:
            if k not in i[0]:
                i[0].append(k)
                qu.append(k)
    
    for j in i[1]:		# 무거운 것 bfs로 돌면서 완전탐색
        qu.append(j)
    while qu:
        x = qu.popleft()
        for k in beads[x][1]:
            if k not in i[1]:
                i[1].append(k)
                qu.append(k)
    
	if len(i[0]) > N//2 or len(i[1]) > N//2: #문제의 조건 중 N이 홀수라고 했으므로 lig나 hev 둘 중 하나가 N//2보다 크다면 중간값이 될 수 없음
        ans += 1
print(ans)

tong39 2년 전 0

해결했습니다.

문제의 조건 상 저울에 올려 본 쌍의 개수 M의 갯수만 맞으면 중복이 있어도 상관이 없는 것 같네요.

반례)

5 4
2 1
2 1
2 1
2 1

ans)

output)

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

문제

문제

출처

ICPC

파이썬 반례나 틀린 부분 요청드립니다.

tong39 2년 전 0

tong39 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말