[백준/BOJ] - 2606번 python 풀이 - 첫 DFS 문제

---

Key Point

1. dfs, bfs 등 그래프 탐색 문제를 통해 해결 가능한 문제이다.

2. 1번 컴퓨터부터 시작하지만 본인은 cnt에 포함하지 않는다.

 

알게 된 점

- 인접한 노드의 쌍이 주어지면 양쪽 노드의 입장을 생각하여 append 해주어야한다. (1번하고 순서 바꿔서 1번 더)

visted = [False] * (n+1) # +1 하는 이유는 0번 idx도 존재하기 때문
- 배열 하나에 False라는 값이 n+1개 append된다.

network=[[]* 0 for _ in range(n+1)] #0번 안쓰니까 1 늘려줌
- 해당 문법을 사용하면 반복문 앞에 숫자는 어떤 값이 와도 상관 없고 몇번 도는지에 따라
리스트 속 리스트 개수가 달라진다.

 

 

---

import sys
input = sys.stdin.readline

n = int(input())
pair = int(input())
cnt = 0
visited = [False]*(n+1) #0번도 생각해서 하나 더 만들기
network=[[]* 0 for _ in range(n+1)] #0번 안쓰니까 1 늘려줌

def dfs(graph, v, visited): #dfs 함수    
    global cnt #전역 변수 cnt 가져오기
    visited[v] = True #노드를 방문 처리한다.       

    for i in graph[v]: #해당 노드 근처에 어떤 노드들이 있는지 확인한다.
        if not visited[i]: #그 노드가 방문처리 되지 않았다면
            dfs(graph,i,visited) #재귀적 호출을 한다.
            cnt+=1 #자기 자신(1번 computer)을 cnt 하지 않음

for i in range(1, pair+1): #1번 index(노드) 부터 들어가게 할 거임
    a, b =list(map(int,input().split())) 
    network[a].append(b) #a의 입장에선 b의 노드 또한 넣어주어야 한다.
    network[b].append(a) #b의 입장에선 a의 노드 또한 넣어주어야 한다.

dfs(network,1,visited) #dfs 호출
print(cnt)