BOJ / 1697번 / 숨바꼭질 [Go][Python3]

👩🏻‍💻 문제

1697번: 숨바꼭질

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/1697
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, k int
	fmt.Fscanln(reader, &n, &k)
	var visited = make([]int, 100001)
	bfs(visited, n, k)
	fmt.Fprintln(writer, visited[k])
}

func bfs(visited []int, start, end int) {
	var queue = []int{start}
	for len(queue) > 0 {
		curPos := queue[0]
		if curPos == end {
			break
		}
		queue = queue[1:]
		if curPos-1 >= 0 && visited[curPos-1] == 0 {
			queue = append(queue, curPos-1)
			visited[curPos-1] += (visited[curPos] + 1)
		}
		if curPos+1 <= 100000 && visited[curPos+1] == 0 {
			queue = append(queue, curPos+1)
			visited[curPos+1] += (visited[curPos] + 1)
		}
		if curPos*2 <= 100000 && visited[curPos*2] == 0 {
			queue = append(queue, curPos*2)
			visited[curPos*2] += (visited[curPos] + 1)
		}
	}
}

🎨 Python3

# https://www.acmicpc.net/problem/1697
import sys

def bfs(visited, start, end):
    queue = [start]
    while len(queue) > 0:
        cur_pos = queue.pop(0)
        if cur_pos == end:
            break
        if cur_pos-1 >= 0 and visited[cur_pos-1] == 0:
            queue.append(cur_pos-1)
            visited[cur_pos-1] += (visited[cur_pos]+1)
        if cur_pos+1 <= 100000 and visited[cur_pos+1] == 0:
            queue.append(cur_pos+1)
            visited[cur_pos+1] += (visited[cur_pos]+1)
        if cur_pos*2 <= 100000 and visited[cur_pos*2] == 0:
            queue.append(cur_pos*2)
            visited[cur_pos*2] += (visited[cur_pos]+1)

if __name__ == "__main__":
    n, k = list(map(int, sys.stdin.readline().split()))
    visited = [0 for _ in range(100001)]
    bfs(visited, n, k)
    print(visited[k])