99클럽 코테 스터디 4기 10일차 TIL - 백준: 특정 거리의 도시 찾기(18352) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	18352	특정 거리의 도시 찾기	BFS	실버2	Swift, Python

🚀 나의 접근 방법

이 문제는 최단 거리를 찾는 문제로 BFS를 사용해야겠다는 것은 금방 알아차릴 수 있다.

다만 주의할 것은 양방향 그래프가 아닌 단방향 그래프이다!

때문에 인접 행렬을 만들 때 양방향으로 해줄 필요 없이 단반향으로 저장하면 된다.

보통 양방향으로 하면 아래와 같이 하는데

for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    let (u, v) = (input[0], input[1])
    graph[u].append(v)
    graph[v].append(u) // 반대 방향도 추가해 줌
}

단방향으로 하면 아래와 같이 하면 된다.

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

이것만 주의하고 나머지는 다른 기본 BFS 문제와 같이 탐색을 구현하고, 최단 거리를 새로운 노드를 방문할 때마다 계산하고 비교하면 된다.

✍️ 나의 코드

Swift

효율적인 BFS를 위해 index(idx)로 큐(array) 접근

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

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)
}

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

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

bfs(X, 0)

if result.isEmpty {
    print(-1)
} else {
    print(result.sorted().map{ String($0) }.joined(separator: "\n"))
}

Python

효율적인 BFS를 위해 deque 사용

from collections import deque

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

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

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

visited = [False] * (N + 1)
result = []

def bfs(v, count):
    queue = deque([(v, count)])
    visited[v] = True

    while len(queue) > 0:
        n = queue.popleft()

        if n[1] == K:
            result.append(n[0])

        for i in graph[n[0]]:
            if not visited[i]:
                queue.append((i, n[1] + 1))
                visited[i] = True
                
bfs(X, 0)

if result: print("\n".join(map(str, sorted(result))))
else: print(-1)

🤔 회고 및 개선사항

어제에 이어 오늘도 BFS 문제가 나와서 그런지 어렵지 않게 해결할 수 있었다. 물론 단방향 그래프가 나왔지만 바로 이해할 수 있었다.

Python join function

python에서 join 함수를 사용하면 리스트를 문자열로 합칠 수 있다. 리스트를 출력할 때 자주 사용되므로 기억해두자.
"구분자".join(리스트) 형식으로 사용한다.

a = ['Hello', 'world', '!!']

result1 = "_".join(a)
print(result1) # Hello_world_!!

result2 = "\n".join(a)
print(result2)
# Hello
# world
# !!