Python 백준 24479 - 알고리즘 수업 - 깊이 우선 탐색 1

백준 링크

https://www.acmicpc.net/problem/24479

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

---

문제

입력

출력

입출력 예시

---

제출한 코드

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split())

# DFS 사용을 위한 2중배열과 방문배열 초기화
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)

cnt = 1

def dfs(graph, v, visited):
    global cnt
    # 방문 순서 확인
    visited[v] = cnt

    for i in graph[v]:
        # 재귀 호출 조건
        if visited[i] == 0:
            cnt += 1
            dfs(graph, i, visited)


# 그래프 값 입력 받기
for i in range(m):
    a, b = (map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

# 그래프 정렬하기
for i in range(n + 1):
    graph[i].sort()

dfs(graph, r, visited)

for i in range(1, n + 1):
    print(visited[i])

 

기본적인 DFS문제이다.

 

조건 1. 모든 가중치는 1로 동일하다.

조건 2. 방문하지 않은 노드는 0으로 마지막에 출력한다.

조건 3. 인접 정점은 오름차순으로 방문한다. ( 정렬을 하라 )

 

1. DFS를 이용할 graph[][]와 visited[]를 초기화해준다.

2. 입력받는 간선들의 정보만 저장한다.

3. 그래프를 정렬한다.

4. DFS를 실행한다.

5. 마지막으로 접근하지 못한 노드의 수 만큼 0을 출력한다.