알고리즘

[백준] 24479 알고리즘 수업 - 깊이 우선 탐색 1 - 실버 2

swanzzz 2025. 4. 24. 21:18
반응형

[오늘의 문제]

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

[오늘의 학습 키워드]

  • 깊이 우선 탐색, 정렬

1. 문제설명

정점의 수 N, 간선의 수 M, 시작 정점 R이 주어지고

다음 M개의 줄에 간선 정보 u, v가 주어집니다.

간선은 가중치가 1인 양방향 간선입니다.

 

이때 간선을 깊이 우선 탐색으로 방문할 때 그 순서를 출력하는 프로그램을 작성해야 합니다.

 

또 인접한 정점이 2개 이상이라면 오름차순으로 방문 처리를 실시해 줍니다.

[제한사항]

  • 시간 제한 1초
  • 메모리 제한 512MB
  • 5 ≤ N ≤ 100,000
  • 1 ≤ M ≤ 200,000
  • 1 ≤ R ≤ N
  • 1 ≤ u < v ≤ N, u ≠ v

2. 접근방식

주어진 조건대로 그대로 깊이 우선 탐색으로 구현하면 됩니다.

 

1. 양방향 간선이므로 주어진 간선의 정보 u, v를 각각 저장해 줍니다.

2. 인접한 정점을 오름차순으로 방문하니 그래프의 인접한 정점 방문 순서를 오름차순으로 정렬해 줍니다.

3. 시작 정점을 기준으로 DFS 탐색 재귀를 시작합니다.

4. 간선의 연결 정보를 토대로 방문 배열을 이용해 방문 처리를 실시하는데 이 visited 배열에는 방문 순서를 저장해 줍니다.

5. 방문 순서는 global 변수를 이용해 DFS로 재귀가 발생하여도 순서가 보장되도록 작성해 줍니다.

 

이 순서대로 구현하면 될 것 같습니다.

3. 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)    # 재귀 깊이 조절

# 시작 위치 1번 -> DFS 마다 count 넘겨주면 방문 처리가 꼬일 수도 있음
count = 1
def DFS(node):
    global count
    visited[node] = count
    # 그래프 연결 정보 불러와서 방문 처리
    for next in graph[node]:
        if visited[next] == 0:
            count += 1
            DFS(next)   # 재귀 탐색

# 정점의 수, 간선의 수, 시작 정점
N, M, R = map(int, input().split())

# 간선의 연결 정보 저장 -> 양방향
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 오름차순 정렬
for i in range(1, N+1):
    graph[i].sort()

# 방문처리용 visited 배열
visited = [0] * (N + 1)
DFS(R)

# 정답출력
for i in range(1, N + 1):
    print(visited[i])

 

[코드설명]

# 정점의 수, 간선의 수, 시작 정점
N, M, R = map(int, input().split())

# 간선의 연결 정보 저장 -> 양방향
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 오름차순 정렬
for i in range(1, N+1):
    graph[i].sort()

 

정점의 수, 간선의 수, 시작 정점을 입력받고 이를 토대로 간선 정보를 저장할 graph 배열을 만들어 줍니다.

 

이때 방문 순서를 보장하기 위해 N + 1 개의 길이로 생성해 입력받는 간선의 정보를 저장해 줍니다.

 

양방향으로 간선의 정보를 저장하고 그래프를 2차원 배열로 생성했으니 배열마다 오름차순으로 정렬해 줍니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)    # 재귀 깊이 조절

# 시작 위치 1번 -> DFS 마다 count 넘겨주면 방문 처리가 꼬일 수도 있음
count = 1
def DFS(node):
    global count
    visited[node] = count
    # 그래프 연결 정보 불러와서 방문 처리
    for next in graph[node]:
        if visited[next] == 0:
            count += 1
            DFS(next)   # 재귀 탐색

# 방문처리용 visited 배열
visited = [0] * (N + 1)
DFS(R)

 

방문 처리를 실시할 visited 배열을 생성해 주는데 동일하게 N + 1 개로 생성해 배열의 길이를 맞춰줍니다.

 

방문 순서를 처리하기 위해 global 키워드로 count를 선언해 주고, 방문 처리를 실시할 때만 count를 증가시켜 줍니다.

 

간선의 연결 정보는 graph의 입력받은 node에 저장되어 있으니 이를통해 다음 노드인 next를 뽑아 옵니다.

 

재귀로 DFS 탐색을 실시하는데 그냥 재귀를 실시하면 파이썬 특성상 최대 1000회만 수행하니 재귀의 깊이를 조절하기 위해 10 ^ 6 제곱으로 설정해 줍니다.

 

그 후 순서대로 visited를 출력해 주었습니다.

4. 결과

[회고]

이번 문제는 어렵다기 보다는 조금 까다로웠던 문제입니다.

 

문제의 설명을 읽다가 정점 번호 1번을 보고 시작 정점이 무조건 1번이라 생각해서 처음 제출을 틀렸습니다.

 

다음은 재귀 에러가 나와서 재귀의 깊이를 10^5 제곱으로 늘려서 실시했는데 틀렸습니다.

 

무방향 그래프라 처음에는 graph[a].append(b) 만 실시했는데 여기서 오류가 발생했어서 틀렸었고 마지막은 DFS로 재귀를 실시할 때 마다 count를 증가시켜 넘겨주었는데 그렇게 하니 방문 순서가 틀릴수 있었습니다.

 

모든걸 수정 후 이제는 통과되겠지 했는데 시간 초과가 나서 간단히 input 하나를 추가했는데 85%에서 재귀 에러가 발생했습니다.

 

최종적으로 재귀의 깊으로 10^6 제곱으로 설정하고, readline을 사용해서 시간과 재귀를 맞출 수 있었습니다.

 

그래프 탐색의 경우 항상 BFS를 더 많이 사용했어서 다시금 DFS로 문제를 해결하려니 생각보다 헷갈리는 부분이 있었습니다.

 

그래도 순서를 잘 생각하며 문제를 풀고 조건을 다시금 하나하나 세워나가보니 문제를 해결할 수 있었습니다.

반응형