반응형
https://www.acmicpc.net/problem/24479
알고리즘 수업 - 깊이 우선 탐색 1 문제
DFS를 이용하여 그래프를 직접 탐색해보는 문제
재귀를 활용하여 DFS를 구성하면 쉽게 해결 할 수 있다.
내가 푼 정답코드
def dfs(t):
global cnt
visited[t] = cnt
line[t].sort()
for i in line[t]:
if visited[i] == 0:
cnt += 1
dfs(i)
import sys
sys.setrecursionlimit(150000)
N, M, R = map(int, sys.stdin.readline().split())
line = [[] for _ in range(N+1)]
visited = [0]*(N+1) # 저장값
cnt = 1
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
line[a].append(b) # 양 방향 간선
line[b].append(a) # 양 방향 간선
dfs(R)
for i in range(1, N+1):
print(visited[i])
문제에서 주어진 조건대로 오르차순으로 정렬해주기 위해서 sort를 해주었다.
방문 순서를 체크해야 하니까 몇번대로 방문하는지 알기 위해서 cnt 변수를 통해 몇번 순서로 방문하는지를 visited에 넣어서 확인해주는 방법으로 구성하였다
느낀 점
DFS를 구성해보는 가장 기초적인 문제이다. 맨날 BFS만 연습하다가 DFS로 풀어보니 원리는 비슷한데 BFS만 하던 습관이 있어서 처음에는 헷갈렸던거 같다.
생각보다 DFS를 직접 구성해보는 연습을 하기에 좋은 문제였다
반응형
'알고리즘 풀이 > 백준' 카테고리의 다른 글
[백준 1244] 스위치 켜고 끄기 (python) (0) | 2023.03.15 |
---|---|
[백준 9663] N-Queen (python) (0) | 2023.03.12 |
[백준 12851] 숨바꼭질 2 (python) (0) | 2023.03.09 |
[백준 1063] 킹 (python) (0) | 2023.03.09 |
[백준 1004] 어린 왕자 (python) (0) | 2023.03.08 |
댓글