백준_2606 (바이러스_BFS DFS 뼈대문제)

• 링크 : https://www.acmicpc.net/problem/2606

---

일단 프로그래머스에 BFS DFS 뼈대문제랑 같은 맥락으로 접근하면 될듯

바깥에 (sol())에 큰 for문이 있었는데 여기선 그게 필요없고
dfs 한 번만 수행하면 될거같다(bfs해도 되긴 한데 dfs하면 될듯)

=> dfs의 return값으로 answer값을 도출(answer는 dfs 수행해서 visit한 수)
=> 즉, DFS 1회만 수행하면 된다.(<-> 프그스 DFS BFS 뼈대문제는 DFS 수행한 횟수만큼 네트워크가 생성된 것)

---

def dfs(s, graph, visit, answer):
    visit[s] = True
    for i in graph[s]:
        if not visit[i]:
            answer += 1                             # 노드 하나 방문할 때 체크 + 1
            answer = dfs(i, graph, visit, answer)
                
    return answer

answer = 0
n = int(input())
visit = [False] * (n+1)

# <중요중요> graph 생성 (m입력 후 edge 기반으로 생성)
graph = [[] for _ in range(n+1)]
for i in range(int(input())):
    A, B = map(int,input().split())               # edge 읽기
    graph[A].append(B)
    graph[B].append(A)
    
print(dfs(1, graph, visit, answer))               # DFS 1회만 수행하면 된다

print(graph)

---

''' 다른 사람 풀이 - 처음에 내가 생각했던 방식 '''
''' => DFS 후 visit = [] 에서 True인 것의 개수만 파악하면 되는 방식 '''
import sys
input = sys.stdin.readline

com = int(input())
visit = [0]*(com+1)
com_list = [[] for _ in range(com+1)]

def dfs(w):
    visit[w] = 1
    for i in com_list[w]:
        if visit[i] == 0:
            dfs(i)

def main():
    N = int(input())    
    
    for i in range(N):
        a,b = map(int,input().split())
        com_list[a].append(b)
        com_list[b].append(a)

    dfs(1)
    print(visit.count(1)-1)

main()