백준 1697. 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

수빈이는 걸을때는 1만큼, 순간이동 할때는 현재 위치의 *2 만큼 갈수 있으므로, 

그래프를 그린다면 아래와 같을 것이다. 

같은 행에서는 걸을때 (1만큼 이동), 아래 행으로 이동할때는 *2 만큼.

 

예를들어 현재 위치가 [0][5]라면 걸을때는 1만큼 이동이므로 같은 행의 [0][4], [0][6]과 이어져있고,

순간이동을 한다면 *2 만큼 이동하므로 아래행인 [1][10]과 이어져있다.

 

 

배열의 크기는 일단 열의 크기는 N과 K의 최댓값인 100000이상은 되어야하고

행의 크기는 아래로 이동(순간이동)할때마다 두배씩 커지므로 2^20 = 1,048,576 이므로 20이면 충분하다.

 

다음 인덱스로 넘어갈때 이용할 dr, dc 배열은 왼쪽,오른쪽,아래로 이동하므로 (위로는 갈 필요가 없다) 크기는 3이다.

dr[2] = 1, dc[2] = 2 인 이유는, 내려갈때 행으로는 1을 더해야하고 열은 2를 곱해야해서 그렇다.

따라서 인덱스를 넘어갈때 왼쪽,오른쪽 이동과 아래로 이동은 연산을 다르게 처리해줘야 한다.

 

#include <iostream>
using namespace std;
#include <queue>
#define MAX 100001
#include <utility>

int N, K;
int mark[20][MAX]; // 2^20 = 10만넘으므로 행의 크기는 20으로 해줘도 충분 
// 내려갈때는 행방향으로 1만큼가고 열은 2를 곱해야함. 
int dr[3] = {0, 0, 1};
int dc[3] = {1, -1, 2}; // right(add), left(add), down(multiply)
int idx = 1;

void bfs(int start) {

    queue<pair<int,int>> q;
    q.push(make_pair(0, start));
    mark[0][start] = idx;

    while(!q.empty()) {
        int nr = q.front().first;
        int nc = q.front().second;
        //cout << "nr: " << nr << ' ' << "nc: " << nc << endl;
        q.pop();
        if(mark[nr][nc] > idx) idx++;

        for(int i = 0; i < 3; i++) {
            int nnr, nnc;
            if(i == 2) { // down(multiply)
                nnr = nr + dr[i];
                nnc = nc * dc[i];
            }
            else {
                nnr = nr + dr[i];
                nnc = nc + dc[i];
            }

            if(nnr < 0 || nnr >= 20 || nnc < 0 || nnc >= MAX) continue;
            if(mark[nnr][nnc] != 0) continue;
            q.push(make_pair(nnr,nnc));
            mark[nnr][nnc] = idx + 1;
        }
    }

}

int main() {

    cin >> N >> K;

    bfs(N);

    int ans = MAX;
    for(int i = 0; i < 20; i++) {
        ans = min(ans, mark[i][K]);
    }

    cout << ans - 1;
}

 

 

---

다른 분들이 푼 방법을 둘러봤는데, 그냥 1차원 배열로 풀면 되는 것이었다.

나는 2차원으로 만들어서 풀었는데 생각해보면 순간이동을 해서 x2만큼 이동할때 아래 행으로 이동할 이유가 없다.

그냥 같은 열에 두배만큼 이동하면 된다.

 

그리고 q에넣을때 pair로 현재 위치와, 깊이를 넣어주고

마지막에 dept를 출력해면 답이다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100001

queue<pair<int, int>> q;
bool mark[MAX];
int N,K,result;
int nextmove[3] = {1, -1, 2};

void bfs(int start) {
    q.push({start,0});
    mark[start] = true;

    while(!q.empty()) {
        int loc = q.front().first;
        int depth = q.front().second;
        q.pop();

        if(loc == K) {
            result = depth;
            break;
        }

        for(int i = 0; i < 3; i++) {
            int next_loc;
            if(i == 2) next_loc = loc * nextmove[i];
            else next_loc = loc + nextmove[i];

            if(next_loc < 0 || next_loc > MAX) continue;
            if(!mark[next_loc]) { // not visited yet
                mark[next_loc] = true;
                q.push({next_loc, depth+1});
            }
        }
    }
}

int main() {
    cin >> N >> K;

    bfs(N);

    cout << result;
}

 

---

2021.04.16 추가

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100001

int N,K;
int arr[MAX];
int mark[MAX];
int idx = 1;
int dc[3] = {-1, 1, 2}; /* 좌측1칸, 우측1칸, 두배(곱하기) */

void bfs() {
    queue<int> q;
    q.push(N);
    mark[N] = idx;

    while(!q.empty()) {
        int c = q.front();
        q.pop();
        if(mark[c] > idx) idx++;

        for(int i = 0; i < 3; i++) {
            int nc;
            if(i == 2) { /* 순간이동, 곱하기 */
                nc = c * dc[i];
            }
            else { /* 좌측, 우측 1칸 이동 */
                nc = c + dc[i];
            }

            if(nc < 0 || nc > MAX) continue;
            if(mark[nc] == 0) {
                mark[nc] = idx + 1;
                q.push(nc);
            }

        }
    }
}

int main() {
    cin >> N >> K;
    bfs();

    cout << mark[K]-1;

}