[백준] 1697번 : 숨바꼭질

문제

 

---

풀이

 

얼핏보면 동적계획법 문제라고 생각할 수도 있다.

하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다.

 

현재 지점(X)의 X-1, X+1, 2X가 아직 방문한 적 없는 좌표라면 X까지 오는데 걸린 시간에 1을 더해 갱신하면 된다.

 

myunji.tistory.com/284

[백준] 2178번 : 미로 탐색

이 문제에서 상하좌우만 뺀거라고 생각해도 된다.

---

소스코드

 

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 100000;
int pos[MAX + 1];
queue<int> q;

void bfsPromising(int source, int dest) {
    if ((dest >= 0) && (dest <= MAX) && (pos[dest] == 0)) { //방문한 적 없는 좌표
        pos[dest] = pos[source] + 1; //여기까지 오는데 걸리는 최소 시간
        q.push(dest);
    }
}

int bfs(int start, int end) {
    q.push(start);
    while (pos[end] == 0) { //도착지점 방문하면 반복 종료
        int cur = q.front();
        q.pop();
        bfsPromising(cur, cur - 1); //X-1
        bfsPromising(cur, cur + 1); //X+1
        bfsPromising(cur, cur * 2); //X*2
    }
    return pos[end] - 1; //시작점을 1로 시작했으니까 1을 빼줌
}

int main() {
    int N, K;

    cin >> N >> K;
    pos[N] = 1; //시작점 방문 표시
    cout << bfs(N, K);
}

전체 소스코드다.

 

    pos[N] = 1; //시작점 방문 표시

이걸 하지 않아서 몇번 틀렸다.

이렇게 시작점을 갱신하지 않으면 시작점은 계속 0이고 미방문 지점으로 인식될 수 있기 때문에 처음에 갱신해야 한다.

 

int bfs(int start, int end) {
    q.push(start);
    while (pos[end] == 0) { //도착지점 방문하면 반복 종료
        int cur = q.front();
        q.pop();
        bfsPromising(cur, cur - 1); //X-1
        bfsPromising(cur, cur + 1); //X+1
        bfsPromising(cur, cur * 2); //X*2
    }
    return pos[end] - 1; //시작점을 1로 시작했으니까 1을 빼줌
}

bfs 함수이다. 도착지점을 방문 못할 일은 없으므로 방문여부를 종료조건으로 했다.

X-1, X+1, 2X에 대해 bfsPromising 함수를 호출해 방문 가능여부를 확인한다.

 

void bfsPromising(int source, int dest) {
    if ((dest >= 0) && (dest <= MAX) && (pos[dest] == 0)) { //방문한 적 없는 좌표
        pos[dest] = pos[source] + 1; //여기까지 오는데 걸리는 최소 시간
        q.push(dest);
    }
}

2178번과 거의 비슷해서 굳이 설명할 필요는 없을 것 같다.