[99클럽 코테 스터디 11일차 TIL] Yes or yes - 백준 25195

오늘은 DFS/BFS 주제로 DFS와 BFS 모두 활용하여 풀 수 있는 문제였다.

 

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

N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.
투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다.
투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다.
그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.

투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다.
팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.
오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다.
그러다가 Twice의 노래인 "YES or YES" 에서 다음과 같은 가사를 듣게 된다.

조금 쉽게 말하자면
넌 뭘 골라도 날 만나게 될 거야
- Twice, YES or YES 가사 중 일부

투어리스트 곰곰이는 Twice의 노래 가사처럼, 뭘 골라도 팬클럽 곰곰이를 만나게 될 것인지 궁금해졌다.
투어리스트 곰곰이가 어떻게 이동하더라도 팬클럽 곰곰이를 만나게 된다면 "Yes" 를,
팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes" 를 출력하자.

[입력]
첫째 줄에는 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000)
이후 M줄에 걸쳐서 간선의 정보를 나타내는 두 정수 u, v 가 주어진다.
이는 정점 u에서 정점 v로 가는 간선이 있음을 의미한다. (1 ≤ u, v ≤ N, u ≠ v)
이후 M+2번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 개수 S가 주어진다. (1 ≤ S ≤ N)
이후 M+3번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호 s가 차례대로 S개 만큼 주어진다. (1 ≤ s ≤ N)
주어진 그래프는 사이클이 없음이 보장된다. 또한 두 정점을 연결하는 간선은 최대 한 개이다.
팬클럽 곰곰이가 존재하는 정점의 번호는 중복해서 주어지지 않는다.

출처: https://www.acmicpc.net/problem/25195

 

풀이 접근

DFS보다는 BFS가 먼저 떠올라서 BFS로 접근했다.

입력을 왕창 받아준다.

let nm = readLine()!.split(separator: " ").map { Int("\($0)")! }
var graph: [[Int]] = Array(repeating: [], count: nm[0] + 1)
(0..<nm[1]).forEach { _ in
    let line = readLine()!.split(separator: " ").map { Int("\($0)")! }
    graph[line[0]].append(line[1])
}
_ = readLine()

let gomgom = Set(readLine()!.split(separator: " ").map { Int("\($0)")! })
var cache: [Bool] = Array(repeating: false, count: nm[0]+1)
cache[1] = true

 

BFS함수를 작성한다.

시작(1)부터 팬클럽 곰곰이가 대기 중이라면 바로 함수를 종료하고, 한번이라도 끝 정점에 도달하면 탐색을 종료한다.

func bfs() -> String {
    var q: [Int] = [1]
    var p = 0
    // 시작부터 팬클럽 곰곰이를 만났을 때
    if gomgom.contains(1) {
        return "Yes"
    }
    
    while p < q.count {
        let point = q[p]
        p += 1
        // 끝 정점 도착 시
        if graph[point].isEmpty {
            return "yes"
        }
        for n in graph[point] {
            if !cache[n] && !gomgom.contains(n) {
                cache[n] = true // 방문 여부 표시
                q.append(n)
            }
        }
    }
    return "Yes"
}

출력한다.

print(bfs())

최종 코드 - Swift

let nm = readLine()!.split(separator: " ").map { Int("\($0)")! }
var graph: [[Int]] = Array(repeating: [], count: nm[0] + 1)
(0..<nm[1]).forEach { _ in
    let line = readLine()!.split(separator: " ").map { Int("\($0)")! }
    graph[line[0]].append(line[1])
}
_ = readLine()

let gomgom = Set(readLine()!.split(separator: " ").map { Int("\($0)")! })
var cache: [Bool] = Array(repeating: false, count: nm[0]+1)
cache[1] = true

func bfs() -> String {
    var q: [Int] = [1]
    var p = 0
    if gomgom.contains(1) {
        return "Yes"
    }
    while p < q.count {
        let point = q[p]
        p += 1
        if graph[point].isEmpty{
            return "yes"
        }
        for n in graph[point] {
            if !cache[n] && !gomgom.contains(n) {
                cache[n] = true
                q.append(n)
            }
        }
    }
    return "Yes"
}

print(bfs())

최종 코드 - Python3

Queue 를 import하지 않고 그냥 구현해서 해결했다.

n, m = map(int,input().split())
graph = [[] for i in range(n + 1)]
for _ in range(m):
  s, e = map(int,input().split())
  graph[s].append(e)
input()
gomgom = set(map(int,input().split()))
cache = [False] * (n + 1)
cache[1] = True

def bfs(graph, gomgom, cache):
    q = [1]
    p = 0
    if 1 in gomgom:
        return "Yes"
    while p < len(q):
        point = q[p]
        p += 1
        if not graph[point]:
            return "yes"
        for n in graph[point]:
            if not cache[n] and not n in gomgom:
                cache[n] = True
                q.append(n)
    return "Yes"

print(bfs(graph, gomgom, cache))

Conclusion

그리 어렵지 않았다! DFS, BFS에 대한 감이 슬슬 오려고 한다.

초기 조건과 종료 조건에 조금 더 신경써보자.