[bfs/백준] 1707번 : 이분 그래프

- 문제 : https://www.acmicpc.net/problem/1707

 

문제를 봐도 이분 그래프가 무엇인지 이해가 가지 않아 구글링을 했더니, 같은 깊이의 노드들끼리 간선으로 연결되어있지 않은 그래프를 의미한다고 생각했다

 

그래서 노드들이 가질 수 있는 값은 0,1로 생각하고, 연결된 노드 중에 같은 값을 가지고 있으면 이분 그래프가 성립이 안 되므로 False, 그런 노드가 없으면 True를 반환해서 True에 YES, False에 NO를 출력하는 로직을 작성하면 되겠다고 생각했다. 

노드의 값을 확인하는 용도로 result 리스트를 구현했는데, 이렇게 할 필요 없이 visit로 다 해결된다 

 

그리고 for문 돌릴 때 if not visit[i] 확인하는 거 잊지말고 추가하기. 이거 빼면 틀린다 

 

- 정답 풀이 : 

from collections import deque
import sys
input=sys.stdin.readline

def bfs(v):
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in data[x]:
            if visit[i] == visit[x]:
                    return False
            elif not visit[i]:
                visit[i]=-visit[x]
                queue.append(i)
    return True            
                
                            
for _ in range(int(input())):
    n,m=map(int,input().split())
    data=[[] for _ in range(n+1)]
    
    for _ in range(m):
        a,b=map(int,input().split())
        data[a].append(b)
        data[b].append(a)

    visit=[0]*(n+1)
    for i in range(1,n+1):
        if not visit[i]: #여기 추가해줘야 틀리지 않는다!           
            flag=bfs(i)   
            if not flag:
                print("NO")
                break       
    if flag:
        print("YES")

 

- 시도 했던 풀이 :

from collections import deque
import sys
input=sys.stdin.readline

def bfs(v):
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in data[x]:
            if visit[i] and result[x] == result[i]:
                return False
            elif not visit[i] and result[x] ==result[i]:
                visit[i]=1
                result[i]=not result[x]                    
                queue.append(i)
    return True            
                
                            
for _ in range(int(input())):
    n,m=map(int,input().split())
    data=[[] for _ in range(n+1)]
    
    for _ in range(m):
        a,b=map(int,input().split())
        data[a].append(b)
        data[b].append(a)
      
    result=[1]*(n+1)
    visit=[0]*(n+1)
    for i in range(1,n+1):
        flag=bfs(i)   
        if not flag:
            print("NO")
            break       
    if flag:
        print("YES")