[코딩테스트]백준 - 숨바꼭질

Adela·2020년 7월 23일

BFS JavaScript 백준 숨바꼭질 알고리즘 자바스크립트 코딩테스트

백준온라인저지

목록 보기

35/53

숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1
5 17
예제 출력 1
4
힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Silver 2번

문제를 번역한 사람: author6

데이터를 추가한 사람: djm03178

링크

PKU Judge Online

TJU Online Judge

알고리즘 분류

BFS

해결한 코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split(' ');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split(' ');
var n = input[0] / 1
var k = input[1] / 1
class Node {
    constructor(data, next = null) {
        this.data = data
        this.next = next
    }
}

class LinkedListQ {
    constructor() {
        this.head = null
        this.tail = null
        this.size = 0
    }

    push(data) {
        let newNode = new Node(data)
        if (!this.head) {
            this.head = newNode
            this.tail = newNode
            this.size++
        } else {
            let node = new Node(data)
            this.tail.next = node
            this.tail = node
            this.size++
        }
    }

    shift() {
        if (!this.head) {
            return
        }
        if (!this.head.next) {
            this.size--
            return this.head.data
        } else {
            this.head = this.head.next
            this.size--
            return this.head.data
        }
    }

    getSize() {
        return this.size;
    }
}


function findMinWay() {
    var visit = Array(100001).fill(false)
    var q = new LinkedListQ()
    var count = 0
    q.push([n, count])
    visit[n] = true
    while (q.getSize() !== 0) {
        var current = q.shift()
        if (current[0] === k) break
        var a = current[0] - 1
        var b = current[0] + 1
        var c = current[0] * 2
        var countAdd = current[1] + 1
        if (a !== 0 && a > 0 && !visit[a]) {
            visit[a] = true
            q.push([a, countAdd])
        }
        if (b !== 0 && b < 100001 && !visit[b]) {
            visit[b] = true
            q.push([b, countAdd])
        }
        if (c !== 0 && c < 100001 && !visit[c]) {
            visit[c] = true
            q.push([c, countAdd])
        }
    }
    return current[1]
}

if (n < k) {
    console.log(findMinWay())
} else if (n > k) {
    console.log(n - k)
} else {
    console.log(0)
}

알고리즘

※ BFS를 이용하여 푼다.
(참고로 나는 처음 문제를 봤을 때 BFS로 접근해야 하는 줄 몰랐다...)

1. linkedlist 큐를 위한 클래스를 만든다.

노드 클래스를 만든다.

linkedlist 큐 클래스를 만든다.
(코드 참고)

2. BFS를 구현한다.

✔ visit 배열
✔ (linkedlist로 구현한) 큐

위 준비가 다 되었으면 이제 본격적으로 BFS를 구현해보자.

🖐🏻 그래프도 아닌데 어케 BFS로 탐색?
수빈이는 -1만큼, +1만큼 ×2 만큼 움직일 수 있다.
이를 그림으로 다음과 같이 표현할 수 있다.

따라서 현재 위치에서 -1, +1, ×2로 움직여가며 가장 처음으로 동생의 위치에 도착했을 때 얼마나 시간이 걸렸는지를 계산해준다.

2-1. 크기가 100001인, 모든 원소가 false인 visit 배열을 만든다.
👉🏻 N, K는 최대 100000이기 때문이다.
0~100000 까지의 수에 대한 방문 여부를 체크하기 위해 크기가 100001인 배열을 만든다.

2-2. linkedlist 큐를 생성한다.

2-3. 현재 수빈이의 위치와 수빈이가 이동한 시간을 큐에 넣는다.
수빈이의 위치는 n, 이동한 시간은 없으므로 0
👉🏻 [n, 0]을 큐에 넣는다.
해당 위치를 방문했으므로 visit[n] = true로 바꾼다.

2-4. 큐의 첫번째 원소를 빼낸다.
👉🏻 이게 바로 현재 수빈이의 위치

현재 위치에서 -1, +1, *2를 한 값이

0보다 크고

100001보다 작으며

방문 여부가 false 라면

👉🏻 해당 위치를 방문했다는 표시를 하고, 해당 위치와 이동 시간을 +1 해준 후 큐에 넣는다.

2-5. 이를 큐가 빌때까지 반복한다.
단, 만약 현재 수빈이의 위치가 동생의 위치와 같다면 반복문을 종료한다.

2-6. 현재 수빈이의 위치에 함께 계산된 이동 시간을 return한다.

3. N과 K의 값에 따라 BFS 탐색을 한다.

만약 N이 K보다 크면?
수빈이는 -1로만 뒤로 움직일 수 있다.
수빈이의 위치에서 음수는 있을 수 없다.
👉🏻 떨어진 거리만큼 -1 로만 움직여야 하므로, N-K한 값을 출력한다.

만약 N과 K가 같으면?
👉🏻 움직일 필요가 없으므로, 0을 출력한다.

만약 N이 K보다 작으면?
👉🏻 구현한 BFS를 통해 가장 적은 시간을 구하여 해당 값을 출력한다.