[Python] 백준 #1707 이분 그래프 (+) 여러가지 반례들

www.acmicpc.net/problem/1707

1707번: 이분 그래프

+) 틀렸습니다 ! 가 반복적으로 나오는 사람들을 위한 반례 case

 

case 1)

11 
3 1 
2 3   
3 2 
1 3 
2 3   
4 4 
1 2 
2 3 
3 4 
4 2 
3 2 
2 1 
3 2 
4 4 
2 1 
3 2 
4 3 
4 1 
5 2 
1 5 
1 2 
5 2 
1 2 
2 5 
4 3 
1 2 
4 3 
2 3 
4 4 
2 3 
1 4 
3 4 
1 2 
3 3 
1 2 
2 3 
3 1     
2 1 
1 2

 

정답 : 'YES', 'YES', 'NO', 'YES', 'YES', 'YES', 'YES', 'YES', 'YES', 'NO', 'YES'

 

case 2)

1

4 2

1 2

3 4

 

정답 : 'YES'

 

 

 

 

이분 그래프가 뭔지 몰라서 처음에 문제만 읽고 문제를 풀었을 땐 문제를 잘못 이해하는 사태가 발생했다.

구글링해서 검색해본 결과, 이분 그래프란 두개의 서로 이웃하는 정점이 다른 색을 가지면 된다는거였고, 방문을 처리하는 visited 배열을 1,-1,0 이렇게 세가지로 선택하여 두개의 서로 이웃하는 정점의 visited 값이 같으면 NO를 출력하고 break 하는 구조로 코드를 작성하였다.

 

백준 질문에 나와있는 오만가지 반례에 다 알맞게 작동하는데,

 

왜!!!!!! 대체 왜 틀린지 도저히 모르겠어서..

2일동안 이 문제를 보류로 담아두고 자꾸 거슬려서 다시 풀어보았다

밑에는 정말 왜 틀린지 모르겠었던 코드

+) 지금보니 쓸데없는 코드가 한 둘이 아니다..하하

N = int(input())

for i in range(N):

    n, m = map(int, input().split())

    visited = [0 for i in range(0, n)]
    p = 0

    # 그래프 생성
    graph = {i: [] for i in range(1, n + 1)}

    for j in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for key in graph:
        graph[key].sort()
        if not graph[key]:  # 비어있음
            continue

        else:
            if visited[key - 1] == 0:
                visited[key - 1] = 1

            for data in graph[key]:
                if visited[data - 1] == 0:
                    visited[data - 1] = -visited[key - 1]
                else:
                    if visited[data - 1] == visited[key - 1]:
                        print("NO")
                        p = -1
                        break
        if p == -1:
            break

    if p != -1:
        print("YES")

 다시 풀어볼 땐 이전 코드의 생각에 구애받지않도록.. 새로운 백지 상태로 다시 코드를 짜 내려갔다.

 

통과!!!!!!!!!

역시 모든 문제는 집중해서 풀어야한다

from collections import deque
import sys

n = int(sys.stdin.readline().rstrip())

for i in range(n):
    
    que = deque()
    v, e = map(int, sys.stdin.readline().rstrip().split())
    graph = {i: [] for i in range(1, v + 1)}
    visited = [0 for i in range(v)]
    c = 0

    for j in range(e):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        graph[a].append(b)
        graph[b].append(a)

    check = 0  # 처음 애인지 체크
    for j in range(1, v + 1):
        if not graph[j]:
            continue
        else:  # 그래프가 비어있지 않음
            que.append(j)

        while que:
            p = que.popleft()

            if visited[p-1]==0:
                visited[p-1]=1

            for k in graph[p]:
                if visited[k-1]==visited[p-1]:
                    print("NO")
                    c=-1
                    break

                elif visited[k - 1] == 0:
                    visited[k - 1] = -visited[p - 1]
                    que.append(k)
            if c==-1:
                break

        if c == -1:
            break

    if c == 0:
        print("YES")