BOJ 1697. 숨바꼭질

polynomeer·2020년 4월 14일
0

Baekjoon Online Judge

목록 보기
17/20
post-thumbnail

BOJ 1697. 숨바꼭질

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

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

1. 문제 해석

  • 수빈이의 위치:N
  • 동생의 위치:K
  • 동생을 찾는 가장 빠른 시간을 구하는 문제
  • 수빈이가 할 수 있는 행동 (위치:X)
    1) 걷기: X+1 또는 X-1로 이동 (1초)
    2) 순간이동: 2*X로 이동 (1초)

이 문제를 그래프의 문제로 변형하기 위해서는 무엇이 정점이고, 무엇이 간선이 될지 대응해보아야 한다. 먼저, 직관적으로 수빈이와 동생의 위치를 정점으로 생각할 수 있다. 그리고 위치와 위치를 이어주는 간선은 수빈이가 할 수 있는 행동(이동) 이 된다.

수빈이의 위치가 5, 동생의 위치가 17인 경우에 5-10-9-18-17로 4초 만에 동생을 찾을 수 있다.


2. 문제 풀이

  • 큐에 수빈이의 위치를 넣어가면서 이동시킨다.
  • 한 번 방문한 곳은 다시 방문하지 않는 것이 좋기 때문에, 따로 배열에 체크하면서 방문
    check[i] = i를 방문했는지
    dist[i] = i를 몇 번만에 방문했는지(초)

now->next를 갔다고 한다면

if (check[next] == false) { 	// 방문하지 않았다면
    q.push(next);		// 큐에 넣고
    check[next] = true;		// 방문 표시
    dist[next] = dist[now] + 1; // now까지 누적된 값을 next에 더함
}

아래의 그림은 N=5, M=17일때 BFS로 탐색하는 과정을 나타낸다. x-1, x+1, 2*x를 동시에 방문하면서 점점 뻗어나가는 모습을 볼 수 있다. 이렇게 BFS로 dist배열의 값을 모두 채워놓으면 M에 해당하는 인덱스의 값이 최소의 시간이 된다.

BFS로 구현한 코드

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 200000;
bool check[MAX+1];
int dist[MAX+1];

int main() {
    int n, m;
    cin >> n >> m;
    check[n] = true;	// 시작점(수빈이의 위치) 방문 체크
    dist[n] = 0;	// 누적 시간은 0초
    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now-1 >= 0) {			// x-1 범위 체크
            if (check[now-1] == false) {	// 방문 체크
                q.push(now-1);
                check[now-1] = true;
                dist[now-1] = dist[now] + 1;	// 1초만큼 더함
            }
        }
        if (now+1 < MAX) {			// x+1 범위 체크
            if (check[now+1] == false) {	// 방문 체크
                q.push(now+1);
                check[now+1] = true;
                dist[now+1] = dist[now] + 1;	// 1초만큼 더함
            }
        }
        if (now*2 < MAX) {			// 2*x 범위 체크
            if (check[now*2] == false) {	// 방문 체크
                q.push(now*2);
                check[now*2] = true;
                dist[now*2] = dist[now] + 1;	// 1초만큼 더함
            }
        }
    }
    cout << dist[m] << '\n';
    return 0;
}

이때 while문 안에 if문의 순서는 바뀌어도 상관없다. 왜냐하면 어차피 모두 큐에 넣어서 동시에 방문되며, 방문되었다면 그 dist값이 무조건 최소이므로 한번만 방문하면 된다.

그런데 여기서 check배열은 굳이 사용할 필요가 없다. 왜냐하면 dist배열에 값이 없다면 방문하지 않은 것과 같기 때문에 check배열의 역할을 할 수 있기 때문이다. 즉, dist배열의 값으로도 충분히 방문여부를 판단할 수 있다. 단, 처음 시작점에서 0으로 시작하므로 -1로 초기화 해준다.

check배열 제거한 코드

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

const int MAX = 200000;
int dist[MAX+1];

int main() {
    int n, m;
    cin >> n >> m;
    memset(dist, -1, sizeof(dist)); // dist배열을 -1로 초기화
    dist[n] = 0;
    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now*2 < MAX) {
            if (dist[now*2] == -1) {
                q.push(now*2);
                dist[now*2] = dist[now] + 1;
            }
        }
        if (now+1 < MAX) {
            if (dist[now+1] == -1) {
                q.push(now+1);
                dist[now+1] = dist[now] + 1;
            }
        }
        if (now-1 >= 0) {
            if (dist[now-1] == -1) {
                q.push(now-1);
                dist[now-1] = dist[now] + 1;
            }
        }
    }
    cout << dist[m] << '\n';
    return 0;
}
profile
어려운 문제를 어렵지 않게.

0개의 댓글