[DFS/BFS] 백준 - 1707번 이분그래프

백준 - 1707번 이분그래프

😢 문제 요약

이분그래프 인지 아닌지 확인하여라. 즉 a라는 노드와 연결된 노드는 반드시 다른 속성을 지녀야 한다.

👍 key point

dfs나 bfs를 통해 a라는 노드가 지닌 값(1)와 연결된 노드가 지닌 값(-1)이 달라야 하며 만일 같을 경우 NO를 출력한다. 필자는 bfs 로 풀어 보았다. 이 문제 풀이의 핵심은 dfs나 bfs로 먼저 방문을 완료한 후 그 다음에 노드의 속성값을 비교하는 것이다. 그렇게 풀지 않을 경우 다 시간초과가 뜨는 것 같다. (필자가 이것 때문에 고생을 좀 했다. ㅜㅜㅜ)

👏 틀린 코드(메모리 초과 - dfs)

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

n = int(input())

def dfs(v,cnt):
    
    visited[v] = cnt

    for i in graph[v]:
        # 방문을 완료하지 않았다면
        if visited[i] == 0:
                       
            if not dfs(i,-cnt):
                return False
        # 방문을 완료했다면 다시 not dfs(i,-cnt)구문을 통해 다시 비교한다. 
        elif visited[i] == visited[v]:   #연결된 두 노드의 값 비교
            
            return False    
        print(i,v)
        
    return True

for _ in range(n):
    v,e = map(int, input().split())
    
    graph = [[] for _ in range(v+1)]

    visited = [0] * (v+1)

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

    result = True

    for i in range(1,v+1):
        
        if visited[i] == 0:
           
            result = dfs(i,1)
            
            if not result:
                break
                 
    print("YES" if result else "NO")

😂 정답 코드(used by bfs)

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

def bfs(v):
    visited[v] = 1
    q = deque()
    q.append(v)

    while q:
        x = q.popleft()
        for i in graph[x]:
            # 아직 방문하지 않았다면 
            if visited[i] == 0:
                visited[i] = -visited[x]
                q.append(i)
            
            # 방문했다면    
            else:
                # 옆에 붙어있는 두 노드가 값이 같다면 False
                if visited[i] == visited[x]:
        
                    return False
    return True                

for _ in range(n):
    v,e = map(int, input().split())
    
    graph = [[] for _ in range(v+1)]

    visited = [0] * (v+1)

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

    result = True

    for i in range(1,v+1):
        
        if visited[i] == 0:
           
            result = bfs(i)
            if not result:
                break
                 
    print("YES" if result else "NO")