728x90
분류가 트리인 문제. 방문처리를 해주는 리스트인 visit을 1차원 배열로 만들어야 한다.
import sys
from collections import deque
t = int(sys.stdin.readline())
for _ in range(t):
n, m = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1)]
visit = [False]*(n+1)
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
cnt = 0
def bfs(v):
global cnt
q = deque()
q.append(v)
visit[v] = True
while q:
x = q.popleft()
for i in graph[x]:
if not visit[i]:
visit[i] = True
q.append(i)
cnt += 1
return cnt
print(bfs(1))
bfs로 풀었는데 dfs로 풀어도 상관없을것 같다.
모든 노드는 서로 연결되어 있다. 그래서 시작점을 1로 시작해도 되고 다른 노드에서 시작해도 된다.
728x90
'[PS(Problem Solving)] > [백준]' 카테고리의 다른 글
[백준] 9205 파이썬(python) : 맥주 마시면서 걸어가기 - (★) (0) | 2022.08.13 |
---|---|
[백준] 2583 파이썬(python) : 영역 구하기 - (범위색칠) (0) | 2022.08.12 |
[백준] 2745 파이썬(python) : 진법 변환 (0) | 2022.08.10 |
[백준] 1026 파이썬(python) : 보물 (0) | 2022.08.09 |
[백준] 1373 파이썬(python) : 2진수 8진수 (0) | 2022.08.08 |