💡그래프 탐색에는 BFS가 더 좋다
DFS : 경우의 수를 탐색하는 방법
BFS : 노드와 노드의 관계를 탐색하는 방법
https://www.acmicpc.net/problem/2606
sol) 1번 컴퓨터와 네트워크 상 연결되어있는 컴퓨터의 수 출력
DFS 풀이
1. 각 노드에서 연결된 컴퓨터 리스트 만들기
#노드 수
n = int(input())
#네트원크 상에서 직접 연결되어 있는 컴퓨터의 쌍의 수
m = int(input())
graph = [[] for _ i in range(n+1)]
for i in range(m) :
a,b = map(int,input().split())
#만일 a가 b와 연결되어 있을 경우 b포함
graph[a].append(b)
#만일 b가 a와 연결되어 있을 경우 a 포함
graph[b].append(a)
2. visited를 설정하여 방문 여부를 판단
visited = [0 for i in range(n+1)]
def recur(node) :
#방문처리
visited[node] = 1
for nxt in graph[node]:
#만일 방문한 적이 있는 경우 넘김
if visited[node] == 1 :
continue
recur(nxt)
recur(1)
3. 1번 컴퓨터와 연결되어 있는 수 출력
print(sum(visited)-1)
4. 전체풀이
#DFS
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
#graph[1] = []
#graph[2] = []
visited = [0 for _ in range(n+1)]
#visited[1] = 0 #방문하지 않았을 경우
#visited[1] = 1 #방문했을 경우
for _ in range(m) :
a,b = map(int,input().split())
#그래프 a는 b를 포함하고 있다
graph[a].append(b)
#그래프 b는 a를 포함하고 있다
graph[b].append(a)
def recur(node) :
visited[node] = 1
for nxt in graph[node] :
if visited[nxt] == 1 :
continue
recur(nxt)
recur(1)
print(sum(visited) - 1)
BFS 풀이
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
for _ in range(m) :
a,b = map(int,input().split())
#그래프 a는 b를 포함하고 있다
graph[a].append(b)
#그래프 b는 a를 포함하고 있다
graph[b].append(a)
from collections import deque
q = deque()
q.append(1)
while q > 0 : #q가 0이 된다면 멈춤
node = q.popleft()
visited[node] = 1 #방문처리
for nxt in graph[node] :
if visited[nxt] == 1 :
continue
q.append(nxt)
print(visited)
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[백준] 10815번 숫자카드 - 파이썬 (0) | 2023.10.06 |
---|---|
[백준] 2805번 나무자르기 - 파이썬 (1) | 2023.10.06 |
다이나믹 프로그래밍 - 파이썬 (1) | 2023.10.05 |
[백준] 14501번 퇴사 - 파이썬 (0) | 2023.10.04 |
[백준] 2961번 도영이가 만든 맛있는 음식 - 파이썬 (1) | 2023.10.04 |