99클럽 코테 스터디 4기 5일차 TIL - 백준 알고리즘 수업 - 너비 우선 탐색 1(24444) Swift & Python

ℹ️ 문제 정보

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

🚀 나의 접근 방법

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

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

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

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

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

✍️ 나의 코드

Swift

func bfs(_ v: Int) {
    var queue: [Int] = [v]
    var idx = 0
    visited[v] = count
    
    while idx < queue.count {
        let n = queue[idx]
        
        for i in graph[n] {
            if visited[i] == 0 {
                queue.append(i)
                count += 1
                visited[i] = count
            }
        }
        idx += 1
    }
}

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

bfs(R)

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

Python

from collections import deque

def bfs(v):
    global count
    queue = deque([v])
    visited[v] = count
    
    while queue:
        n = queue.popleft()
        for i in sorted(graph[n]):
            if visited[i] == 0:
                queue.append(i)
                count += 1
                visited[i] = count

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

bfs(R)

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

🤔 회고 및 개선사항

Swift에서 Queue 다루기

Swift에서는 공식적으로 큐 자료구조를 지원하지 않는다. 그리고 Swift에서 Array의 removeFirst() 또는 popFirst()는 O(n)의 시간이 걸린다. 그래서 그냥 위 메소드를 사용하면 문제에서 시간 초과가 날것이다.

이를 해결하기 위한 방법으로 큐를 직접 구현하는 것이 있다. 하지만 시간도 걸리고 코드 양이 많아진다. 그래서 이번에는 Array를 접근하는 index를 사용하여 큐에서 값을 꺼내는 효과를 냈다. 이렇게 되면 큐에서 값은 제거되지 않고 큐의 가장 앞단을 index로 표시해 주면 된다.

Python에서 Queue 다루기

Python도 마찬가지로 기본 List를 사용하면 pop(0) 시 O(n) 시간이 걸린다. 그래서 파이썬에서는 보통 collections 모듈의 deque를 사용한다. double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.

deque는 아래와 같이 생성하고, 첫번째 데이터를 꺼낼수 있다.

>>> from collections import deque
>>>
>>> queue = deque([4, 5, 6])
>>> queue.append(7)
>>> queue
deque([4, 5, 6, 7])
>>> queue.popleft()
4