[백준] 12851 숨바꼭질 2 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

---

2. 풀이 과정

• 문제 해결의 흐름
  1. ⭐️⭐️ 문제의 키포인트는 방문처리이다. 이전 문제인 '1697 숨바꼭질' 문제와 다른 방식으로 방문 처리해 주었다.
  2.  이전 문제는 단순히 '최단 시간'을 구하는 문제였기에 방문 배열에 시간을 저장해도 문제없었지만 이 문제는 최단 시간이 같은 다른 방법들을 모두 구해야 하기 때문이다.
  3.  그렇기에 queue에 {현재 위치, 걸린 시간}을 저장하고 이후에 q.pop()되는 시점에 방문처리를 해준다. ⭐️⭐️ push 되는 시점에 방문처리를 해주게 되면 여러 방법을 못 구하기 때문이다!
  4. ⭐️ 목표 지점인 K에 처음 방문할 경우 최단 시간을 저장해 주고, 재방문할 경우 방법 수가 하나 늘어난 것이며 최단 시간보다 큰 시간의 queue값이 선택된다면 최단 시간 queue값에 대한 탐색이 끝났기에 break 해주자.
• 나의 코드 

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100001

int N, K; // N : 수빈이의 위치, K : 동생의 위치
bool visited[MAX];
int wayNum = 0;

void bfs() {
    queue<pair<int, int> > q;
    q.push(make_pair(N, 0));
    visited[N] = true;  // 시작 위치 방문 처리
    bool first_visit = true;
    int fasted_time = MAX; // 수빈이가 동생을 찾는데 걸린 최소 시간

    while (!q.empty()) {
        int curPosition = q.front().first;
        int time = q.front().second;
        q.pop();
        visited[curPosition] = true;

        // 동생 찾았다면??
        if ((curPosition == K) && first_visit) { // 첫 방문
            wayNum += 1;
            fasted_time = time;
            first_visit = false;
        } else if (!first_visit && curPosition == K && time == fasted_time){ // 첫 방문 X
            wayNum += 1;
        } else if (time > fasted_time) break; // 불필요한 탐색은 더 이상 그만


        int minusPosition = curPosition - 1;
        int plusPosition = curPosition + 1;
        int multiPosition = curPosition * 2;

        // 1. -1
        if (minusPosition >= 0 && !visited[minusPosition]) {
            q.push(make_pair(minusPosition, time + 1));
        }

        // 2. + 1
        if (plusPosition < MAX && !visited[plusPosition]){
            q.push(make_pair(plusPosition, time + 1));
        }

        // 3. * 2
        if (multiPosition < MAX && !visited[multiPosition]) {
            q.push(make_pair(multiPosition, time + 1));
        }
    }

    cout << fasted_time << endl;
    cout << wayNum;
}

int main() {
    cin >> N >> K; // 입력 받기
    fill_n(visited, MAX, false); // 방문 배열 전부 false로 초기화
    bfs();

    return 0;
}

 

• 이 문제를 통해 얻어갈 수 있는 것들
  • bfs는 방문처리가 굉장히 중요하다는 것을 다시 한번 느낀다. 특히 방문처리해주는 위치 또한 굉장히 중요하다!!!

---

3. 후기 

 방문처리의 중요성을 다시 한 번 느끼게 해 준 문제