내 인생 이대로 ㅈ될 수 없다

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를 모두 끝냈다.

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

매일매일 반복해야겠다

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

내 풀이

1)BFS

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    Num_Comp = int(input())
    Connect = int(input())
    graph=[[] for _ in range(Num_Comp+1)]
    visited = [False] * (Num_Comp+1)
    for _ in range(Connect):
        a, b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    count=0
    def bfs(virus):
        nonlocal count
        q = deque([virus])
        

        while q:
            v = q.popleft()
            
            visited[virus] = True

            for i in graph[v]:
                if visited[i] == False:
                    count +=1
                    visited[i]=True
                    q.append(i)

    bfs(1)

    print(count)

solution()

2)DFS

import sys
sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def solution():
    Num_Comp = int(input())
    Connect = int(input())
    graph=[[] for _ in range(Num_Comp+1)]
    visited = [False] * (Num_Comp+1)
    for _ in range(Connect):
        a, b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    count=0
    def dfs(virus):
        nonlocal count
        visited[virus] = True
        for g in graph[virus]:
            if visited[g] == 0:
                count +=1
                dfs(g)
    dfs(1)

    print(count)

solution()

결과론적으로 적어도 내 풀이로는 dfs로 푼게 bfs보다 메모리도 덜 먹고 시간도 덜 걸렸다.

dfs의 단점은 잘못 걸릴경우 속도가 너무 오래걸린다는것인데, 위 문제처럼 큰 깊이가 필요없는 경우에는 당연히 dfs가 더 빠르다. 적어도 지금까지 내가 풀어 본 문제들은 모두 bfs,dfs 둘 다 적용 가능한 경우가 대부분이였는데, 그렇기에 두개 다 풀이 방법을 아는것이 중요한거 같다.

다른사람의 풀이

_,_,*i=open(0)
for _ in(n:=[-1,1]+[0]*99):
 for l in i:a,b=map(int,l.split());n[b]=n[a]=n[a]|n[b]
print(sum(n))

뭐..할말이없다 ㅋㅋ