728x90
나의 풀이(dfs)
import sys
n = int(input())
m = int(input())
graph = [ [] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
visit = [0] * (n+1) #1
cnt = 0
def dfs(v):
global cnt
visit[v] = 1
for i in graph[v]:
if visit[i] == 0:
cnt += 1
dfs(i)
dfs(1) #2
print(cnt)
dfs로 문제를 해결했다. 하지만 bfs로 해결하는 방법도 있다.
#1 : dfs에 빠지면 안되는 방문표시
#2 : 모든 노드는 1에서 시작한다했으니 dfs(1)로 실행
나의 풀이(bfs)
from collections import deque
import sys
n = int(input())
m = int(input())
graph = [ [] for _ in range(n+1) ]
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
visit = [0] * (n+1)
cnt = 0
def bfs():
q = deque()
q.append(1) #1
visit[1] = 1 #2
global cnt
while q:
v = q.popleft()
for i in graph[v]:
if visit[i] == 0:
cnt += 1
visit[i] = 1
q.append(i)
bfs()
print(cnt)
#1 : 1에서부터 시작이니까 q에 1추가
#2 : 첫노드 방문처리
같은 문제지만 bfs와 dfs로 풀어볼 수 있는 문제입니다. 같은 문제도 다르게 풀 수 있어서 좋았습니다.
728x90
'[Coding Test] > [백준]' 카테고리의 다른 글
[백준] 1012 파이썬(python) : 유기농 배추 (0) | 2022.06.30 |
---|---|
[백준] 2667 파이썬(python) : 단지번호붙이기 - (★) (0) | 2022.06.29 |
[백준] 24445 파이썬(python) : 알고리즘 수업 - 너비 우선 탐색 2 (0) | 2022.06.29 |
[백준] 24444 파이썬(python) : 알고리즘 수업 - 너비 우선 탐색 1 (0) | 2022.06.29 |
[백준] 24480 파이썬(python) : 알고리즘 수업 - 깊이 우선 탐색 2 (0) | 2022.06.29 |