99클럽 코테 스터디 4기 11일차 TIL - 백준: Yes or yes(25195) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	25195	Yes or yes	DFS, BFS	골드4	Swift, Python

🚀 나의 접근 방법

이 문제는 골드4로 분류되어 있지만 실버1 또는 골드5가 적당한듯싶다.

그래프 탐색 문제이며 방향 그래프인 점을 주의하여 인접행렬을 정의해야 한다. DFS와 BFS 중 어느 것을 사용해도 상관없지만, 최단 거리를 구하는 것도 아니고 모든 경로를 탐색해야 하기 때문에 DFS를 사용했다.

DFS로 노드들을 방문하면서 해당 노드가 팬클럽 곰곰이가 있는 노드라면 False를 반환한다.

그리고 더 이상 이동할 노드가 없다면(그동안 팬클럽 곰곰이를 만나지 않고 여행을 끝냄) True를 반환한다.

그래서 결국 팬클럽 곰곰이가 있는 노드 이하로는 더 이상 탐색하지 않으며, 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 있다면 dfs()는 최종적으로 True를 반환한다.

✍️ 나의 코드

Swift

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

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

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

let S = Int(readLine()!)!
let ss = readLine()!.split(separator: " ").map{ Int($0)! }

var visited = Array(repeating: false, count: N + 1)

func dfs(_ v: Int) -> Bool {
    visited[v] = true
    
    if ss.contains(v) {
        return false
    }
    
    if graph[v].isEmpty {
        return true
    }
    
    var result = false
    for i in graph[v] {
        if !visited[i] {
            if dfs(i) {
                result = true
            }
        }
    }
    return result
}

if dfs(1) { print("yes")}
else { print("Yes") }

Python

RecursionError를 방지하기 위해 sys.setrecursionlimit() 사용

import sys
sys.setrecursionlimit(10 ** 5)

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

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

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

S = int(input())
ss = list(map(int, input().split(" ")))

visited = [False] * (N + 1)

def dfs(v):
    visited[v] = True

    if v in ss:
        return False
    
    if not graph[v]:
        return True

    result = False
    for i in graph[v]:
        if not visited[i]:
            if dfs(i): result = True
    return result

if dfs(1): print("yes")
else: print("Yes")

🤔