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

레일리·2024년 10월 31일

99클럽 코테 스터디 4기

목록 보기

4/18

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	24479	알고리즘 수업 - 깊이 우선 탐색 1	DFS	실버2	Swift, 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:])))