간만에 올리는 백준 풀이 ㅎㅎ ...
내 안의 백준 화력 ... 죽었다 ...

1. 다른 풀이

1-1. DFS

import sys
input = sys.stdin.readline

n = int(input()) # 전체 컴퓨터 개수
v = int(input()) # 컴퓨터 쌍 개수
graph = [[] for i in range(n+1)] # 컴퓨터 개수만큼 2차원 배열 만들기 (0번 컴퓨터는 없음 -> 접근할 때 쉬우라고!)
visited = [0] * (n+1) # 방문한 컴퓨터인지 표시
for i in range(v):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
def dfs(v):
    visited[v] = 1
    for nx in graph[v]:
        if visited[nx] == 0:
            dfs(nx)

dfs(1)
print(sum(visited)-1)

이 문제는 두 가지로 접근할 수 있는데, 바로 dfs, bfs 이다.
그래서 일단은 나에게 익숙한 dfs 풀이법을 보았다!

for i in range(v):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

처음에 이 부분이 이해가 잘 되지 않았는데, 이 부분은 컴퓨터의 쌍방 연결을 의미한다.
그리고 여기서 visited 변수는 방문했다의 의미도 되지만, 그보다는 감염되었다의 의미이다.

그래서 보면 이 dfs 함수가 실행 되는 첫번째 element가 1인데,
1번 컴퓨터가 감염되었기 때문이다.
그래서 1번에 연결된 컴퓨터에 가서 그 컴퓨터도 visited[v]=1을 해주어 감염되었다는 표시를 하게 된다.

1-2. BFS

import sys
input = sys.stdin.readline

n = int(input()) # 전체 컴퓨터 개수
v = int(input()) # 컴퓨터 쌍 개수
graph = [[] for i in range(n+1)] # 컴퓨터 개수만큼 2차원 배열 만들기 (0번 컴퓨터는 없음 -> 접근할 때 쉬우라고!)
visited = [0] * (n+1) # 방문한 컴퓨터인지 표시
for i in range(v):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
##################### 여기까지는 동일 #######################

from collections import deque
visited[1]=1 # 1번 컴퓨터부터 시작이니 방문 표시
Q=deque([1])
while Q:
    c=Q.popleft()
    for nx in graph[c]:
        if visited[nx]==0:
            Q.append(nx)
            visited[nx]=1
print(sum(visited)-1)

사실 BFS로는 문제를 많이 풀어보지 못해서 직관적이지는 않았지만,
일단 설명은 다음과 같다.
visited[1] = 1 을 통해서 1번 컴퓨터가 감염되었다! 방문했다! 라는 걸 알려준다.
그리고 BFS에서는 deque를 이용하게 된다. deque는 현재 연결된 컴퓨터에서 내가 방문해야 하는 컴퓨터들을 의미한다.
1번 컴퓨터를 예시로 보자.현재 deque에 1번 컴퓨터가 들어갔으니 검사해주어야 하는 값, 즉 이 1을 c에 넣어준다. 해당 변수는 current를 의미하는 변수로, 현재 검사하고 있는 컴퓨터라고 볼 수 있다.
그리고 1번 컴퓨터에 연결된 다른 컴퓨터들이 만약 0이라면, 그 컴퓨터도 검사를 해야하므로 deque에 저장하고 해당 컴퓨터는 감염되었다라는 표시를 해준다.
이런 식의 플로우로 진행하다보면 끝!

풀이를 정리해보면

그래프 풀이법

• 2차원 배열을 통해서 일단 각 요소들의 관계를 정립해준다.
• visited 등의 변수를 통해서 해당 요소의 방문 여부를 체크할 수 있도록 해준다.
• 만약 DFS가 알맞은 풀이일 경우: 재귀 함수 형태로 작성!
• 만약 BFS가 알맞은 풀이일 경우: deque를 이용해 작성!

2. 마치며

근데 DFS를 재귀함수로 푸는 건 직관적인데 BFS를 deque로 푸는 건 왜 아직 직관적이지가 않을까나...
그래도 그리디나 다른 것보다 그래프가 훨씬 재밌는 것 같다 ㅎㅎ