[BOJ] 6118 - 숨바꼭질 (Python, JavaScript)

 

 

아이디어

 

BFS로 1번 헛간과 거리가 가장 먼 헛간들을 찾는다.

 

 

풀이 #1 (Python)

 

방문 표시 및 1번 헛간과의 거리를 저장하기 위해 N+1 크기의 0으로 채워진 리스트 visited를 생성한다.

visited에서 1번 헛간의 값을 1로 저장하고, 큐 queue에 1을 저장한다.

 

while문에서 BFS로 방문하지 않은 주변 헛간으로 이동하며 visted에 1번 헛간과의 거리보다 1 더 큰 값을 저장한다.

모든 헛간을 방문한 후 for문에서 숨어야 하는 헛간 번호 num, 해당 헛간까지의 거리 d, 같은 거리의 헛간 수 cnt를 구한다.

 

import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    visited = [0]*(N+1)
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A].append(B)
        graph[B].append(A)
    visited[1] = 1
    queue = [1]
    while queue:
        idx = queue.pop(0)
        for i in graph[idx]:
            if visited[i] == 0:
                visited[i] = visited[idx]+1
                queue.append(i)
    num = d = cnt = 0
    for i in range(2, N+1):
        if visited[i]-1 > d:
            d = visited[i]-1
            cnt = 1
            num = i
        elif visited[i]-1 == d:
            cnt += 1
    print(num, d, cnt)

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [N, M] = input[0].split(' ').map(Number);
let graph = Array.from(Array(N+1), () => []);
for (let i=1; i<=M; i++) {
    const [A, B] = input[i].split(' ').map(Number);
    graph[A].push(B);
    graph[B].push(A);
}
let visited = Array(N+1).fill(0);
visited[1] = 1;
let queue = [1];
while (queue.length) {
    const idx = queue.shift();
    for (let i of graph[idx]) {
        if (visited[i] == 0) {
            visited[i] = visited[idx]+1;
            queue.push(i);
        }
    }
}
let num = d = cnt = 0;
for (let i=2; i<=N; i++) {
    if (visited[i]-1 > d) {
        d = visited[i]-1;
        cnt = 1;
        num = i;
    }
    else if (visited[i]-1 == d) cnt += 1;
}
console.log(num, d, cnt);