백준 알고리즘 1697 (숨바꼭질) - C++, Python

[문제] 백준 알고리즘 1697 (숨바꼭질)

> https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

N에서 M까지 이동하는데, 1초에 +1이나 -1이나 *2를 이동할 수 있다.

최소 시간을 구하는 문제, BFS 문제이다.

 

[문제 해결]

 

1. BFS를 위해 queue, while, visited를 사용한다.

2. queue에 초기값으로 시간, 위치 n을 push

3. 다음 이동 위치인 +1, -1, *2의 변수를 설정

   +1일 경우는 최대 범위 이하만 만족하면 된다.

   -1일 경우는 0 이상만 만족하면 된다.

   *2일 경우는 최대 범위 +1이하만 만족하면 된다. (+1은 k가 홀수일 경우 포함)

4. 위의 조건을 만족하면, visited를 1, queue에 시간+1, 위치를 push

5. while queue하다가 위치가 k일 때 출력

 

 

[C++]

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

queue< pair<int, int> > q;
const int MAX = 1e5 + 1;
bool visited[MAX];
int n, k;

void solve_bfs() {
	q.push({ 0, n });
	visited[n] = 1;
	while (!q.empty()) {
		int cnt = q.front().first;
		int pos = q.front().second;
		q.pop();
		if (pos == k) {
			printf("%d", cnt);
			return;
		}
		int pos_p = pos + 1;
		int pos_m = pos - 1;
		int pos_d = pos * 2;
		if (pos_d <= k + 1) { // k가 홀수일 때를 고려
			if (!visited[pos_d]) {
				visited[pos_d] = 1;
				q.push({ cnt + 1, pos_d });
			}
		}
		if (0 <= pos_m) {
			if (!visited[pos_m]) {
				visited[pos_m] = 1;
				q.push({ cnt + 1, pos_m });
			}
		}
		if (pos_p <= k) {
			if (!visited[pos_p]) {
				visited[pos_p] = 1;
				q.push({ cnt + 1, pos_p });
			}
		}
	}
	return;
}

int main() {
	memset(visited, 0, sizeof(visited));
	scanf("%d %d", &n, &k);
	solve_bfs();
}

 

[Python]

import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
MAX = 1e5
visited = [0] * int(MAX+1)

def solve_dfs():
    q = deque()
    q.append((0, n))
    visited[n] = 1
    while q:
        cnt, pos = q.popleft()
        pos_p, pos_m, pos_d = pos + 1, pos - 1, pos * 2
        if pos == k:
            print(cnt)
            return
        if pos_d <= MAX+1:
            if not visited[pos_d]:
                visited[pos_d] = 1
                q.append((cnt+1, pos_d))
        if pos_p <= MAX:
            if not visited[pos_p]:
                visited[pos_p] = 1
                q.append((cnt+1, pos_p))
        if 0 <= pos_m:
            if not visited[pos_m]:
                visited[pos_m] = 1
                q.append((cnt+1, pos_m))
solve_dfs()