내가 제일 취약해하는 DFS, BFS 문제이다..
항상 기피하던 알고리즘 중 하나인데 언제까지 피할 수만은 없으니, 기왕이면 며칠간 꾸준히 풀면서 간파해버리자👀‼️

2606번

문제/입력/출력

예제 입력 및 출력

문제 바로가기

백준 2606번

---

💡풀이 방법

우선 해당 문제는 DFS 알고리즘을 이용하였다.
1에서부터 이어지는 모든 컴퓨터들을 방문하여 확인해야한다.

나같이 dfs, bfs 문제에 약한 사람들은 접근 자체를 어떻게 해야할지 막막할 수 있다.
나는 아래와 같은 순서로 접근하였다.

1. 특정 컴퓨터와 이어진 컴퓨터의 숫자값을 각 배열에 추가한다.
   • 예를 들어, 1번이 2번과 이어져 있다면, array_1에 2라는 값을 추가해주고, array_2에는 1을 추가해준다.
2. 컴퓨터 수+1만큼의 length를 가지는 배열(visit)을 선언해준다.
   • 이는 바이러스가 방문했을 경우: 1, 안했다면: 0이 된다.
   • 모든 인덱스의 default값: 0
3. dfs를 통해 visit값을 set한다.
   • array_1부터 시작했을 때, array_1에 들어있는 값은 컴퓨터 1번과 이어져있다는 뜻. 즉, 배열1에 저장되어있는 값의 배열에 방문하여 또 다시 visit값을 1로 set.
   • ex. array_1 = [3,4]라면, visit의 3번째, 4번째의 값을 1로 set하고, array_3에 접근하여 해당 배열에 저장된 숫자 값도 visit값을 1로 set

---

💡구현 코드

1. 특정 컴퓨터와 이어진 컴퓨터의 숫자값을 각 배열에 추가한다.

n = int(input()) #컴퓨터 수 
m = int(input()) #간선 (이어진 쌍의 수)

graph = [[] for _ in range(n+1)] #컴퓨터 수 +1 만큼의 배열

# 간선 수만큼 반복
for i in range(m): 
    x, y = map(int, input().split())

    graph[x].append(y)
    graph[y].append(x)

2. 컴퓨터 수(n)+1만큼의 length를 가지는 배열(visit)을 선언해준다.

• 컴퓨터 수+1만큼으로 지정하는 이유: 컴퓨터 1번이 방문한 값을 확인하려면 인덱스 값과 동일하게 맞춰주는 것이 편하기 때문 (인덱스 1번 == 컴퓨터 1번이 방문한 컴퓨터)

visit = [0] * (n+1)

3. dfs를 통해 visit값을 1로 set한다.

def dfs(graph, v, visited):
    visit[v] = 1
    for i in graph[v]:
        if visit[i] == 0:
            dfs(graph, i, visited)
            
dfs(graph, 1, visit)            

---

👀전체 코드

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]

for i in range(m):
    x, y = map(int, input().split())

    graph[x].append(y)
    graph[y].append(x)

visit = [0] * (n+1)

def dfs(graph, v, visited):
    visit[v] = 1
    for i in graph[v]:
        if visit[i] == 0:
            dfs(graph, i, visited)

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