내 인생 이대로 ㅈ될 수 없다

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))

뭐..할말이없다 ㅋㅋ