내 인생 이대로 ㅈ될 수 없다

https://www.acmicpc.net/problem/1707

내 풀이

1.BFS

import sys
from collections import deque

input = sys.stdin.readline



def bfs(start):
    queue = deque([start])  
    visited[start] = 1   
    while queue:  
        x = queue.popleft()  

        for i in graph[x]:  
            if not visited[i]:  
                queue.append(i)  
                visited[i] = -1 * visited[x]  
            elif visited[i] == visited[x]:  
                return False  
    return True  


for _ in range(int(input())):
    V, E = map(int, input().split())
    graph = [[] for i in range(V + 1)]  
    visited = [False] * (V + 1)  

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

    for i in range(1, V + 1):
        if not visited[i]:  
            result = bfs(i)
            if not result:
                break

    print('YES' if result else 'NO')

우선 문제를 이해하는게 조금 이해가 안됐다. 

내가 이해한 바로는 이렇다.

어떤 노드들을 두 그룹으로 나눌 수 있냐를 판단하는데 

그 기준은 같은 그룹에 있는 인접한 노드들끼리는 간선이 연결 되어 있지 않아야한다.

즉 같은 그룹안에 있는 노드들은 서로 연결이 되어 있으면 안된다.

같은 그룹인지를 판단하기 위해서 visited에 0(방문한적이 없음),1(그룹 1),-1(다른 그룹 -1) 을 할당한다.

같은 그룹일 경우에는 False를 반환한다.

2. DFS

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def solution():
    def dfs(start,group):
        nonlocal error
        if error:
            return

        visited[start] = group

        for i in graph[start]:
            if not visited[i]:
                dfs(i,-group)
            elif visited[start] == visited[i]:
                error = True
                return

    for _ in range(int(input())):
        V, E = map(int, input().split())
        graph = [[] for _ in range(V + 1)]  
        visited = [False] * (V + 1)  
        error = False

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

        for i in range(1, V + 1):
            if not visited[i]:  
                dfs(i, 1)  
                if error:  
                    break  

        if error:
            print('NO')
        else:
            print('YES')

solution()

개인적으로 이 문제는 dfs가 조금 더 직관적인거 같다. 위와 같은 개념이다!

다른사람의 풀이

https://ji-gwang.tistory.com/293

참고 블로그

이 문제를 끝으로 bfs를 모두 끝냈다.

조금 익숙해지긴 했지만 아직까지도 확실하지는 않다.

매일매일 반복해야겠다