99클럽 코테 스터디 4일차 TIL - 백준 알고리즘 수업 - 깊이 우선 탐색 1(24479) Swift & Python

레일리·2024년 10월 31일
0
post-thumbnail

ℹ️ 문제 정보

플랫폼번호제목유형난이도언어
백준24479알고리즘 수업 - 깊이 우선 탐색 1DFS실버2Swift, Python

🚀 나의 접근 방법

문제 유형은 문제 제목에 나타나 있는 것처럼 DFS이다. DFS 연습용 문제여서 어렵게 생각할 건 없고 개념과 문제 조건에 충실하여 코드를 짜면 된다.

먼저 입력되는 간선 정보를 인접 리스트로 그래프를 정의했다.

그리고 문제의 조건에 "정점 번호를 오름차순으로 방문한다"라고 되어 있어 인접 리스트 각 요소를 오름차순으로 정렬해 주었다.

그 이후에는 일반적인 DFS를 구현하였고 각 정점의 방문 순서를 기록하기 위해 count 변수를 정의하고 사용했다.

💡 일반적으로 노드 방문 여부 기록을 위해 visited 배열을 Boolean 타입으로 선언한다. 하지만 이 문제에서는 각 노드(정점)의 방문 순서를 기록할 필요가 있기 때문에 Integer 타입으로 선언했다. 그래서 0인 경우는 방문하지 않은 상태이고 0 이외의 정수이면 방문했다는 표시가 된다.

✍️ 나의 코드

Swift

func dfs(_ v: Int) {
    visited[v] = count

    for i in graph[v] {
        if visited[i] == 0 {
            count += 1
            dfs(i)
        }
    }
}

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let (N, M, R) = (input[0], input[1], input[2])

var graph: [[Int]] = Array(repeating: [], count: N + 1)

for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    graph[input[0]].append(input[1])
    graph[input[1]].append(input[0])
}

graph = graph.map{ $0.sorted() }

var visited: [Int] = Array(repeating: 0, count: N + 1)
var count = 1

dfs(R)

_ = visited[1...].map{ print($0) }

Python

import sys
sys.setrecursionlimit(10 ** 5)

def dfs(v):
    global count
    visited[v] = count
    for i in sorted(graph[v]):
      if visited[i] == 0:
          count += 1
          dfs(i)

N, M, R = map(int, input().split())

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [0] * (N + 1)
count = 1

dfs(R)

print("\n".join(map(str, visited[1:])))

🤔 회고 및 개선사항

Python에서 RecursionError 문제

RecursionError는 재귀와 관련된 에러로 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때 발생한다. BOJ의 채점 서버에서 이 제한 값은 1,000으로 재귀를 돌리기에는 작다.

해결 방법 두 가지있다.
1. 재귀를 반복문으로 구현하기
2. 아래와 같이 sys.setrecursionlimit()로 재귀 최대 깊이 설정하기

import sys
sys.setrecursionlimit(10**6)

주의할 것은 무작정 큰 수를 대입하면 메모리 초과 문제가 발생한다.(그만큼 스택 메모리 영역을 잡아 두기 깨문) 적당한 수를 입력하도록 하자.

profile
나야, 개발자

0개의 댓글