Baekjoon/DFS와 BFS
[백준] 11724 연결 요소의 개수 (실버2) / DFS
hellosonic
2023. 4. 26. 11:58
문제요약



나의 코드 및 설명
- 이차원 리스트에 그래프 정보를 저장한다.
- dfs 함수 : 시작노드를 의미하는 변수 sn과 연결된 노드들의 방문 정보를 체크한다. 만약 방문하지 않은 노드라면 방문 체크하고, 해당 노드에 대한 하위 dfs 함수를 호출한다.
- 메인 함수에서 1번 노드부터 마지막 노드까지 방문하며 아직 방문하지 않은 노드가 있다면 dfs 함수를 호출하고 카운트한다.
import sys
sys.setrecursionlimit(10**4)
def dfs(sn):
for i in board[sn]:
if visited[i] == 0:
visited[i] = sn
dfs(i)
n,m = map(int, input().split())
board = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m):
start, end = map(int ,input().split())
board[start].append(end)
board[end].append(start)
count = 0
#1번노드부터 마지막 노드까지 방문
for i in range(1,n+1):
#만약 해당 노드가 방문 전이라면
if visited[i] == 0:
#방문해서 dfs수행
#노드가 연결되어 있다면 연결된 노드의 방문 테이블은 갱신될 것
dfs(i)
count += 1
print(count)
피드백
DFS 연습을 위해 풀어본 문제. 이 문제는 Pypy로 실행시켜 통과할 수 있었는데, 파이썬으로 실행시켜 통과하기 위해서는 input() 대신 sys.stdin.readline() 을 사용하면 통과할 수 있다고 한다. 코드에는 별 문제가 없이 정상적으로 구현한 것 같아 빠르게 다음 문제로 넘어가도록 하자.