[백준/C++] 1697번 숨바꼭질

1.문제 링크

숨바꼭질

2. 풀이 전 계획과 생각

• dp 이용

3. 풀이

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

bool visited[100001];

int main(){
    int n,k; cin>>n>>k;

    queue<pair<int,int> > q;

    q.push({n, 0});
    visited[n]= true;
    int answer;
    while(true){
        int cn = q.front().first;
        int cnt = q.front().second;

        q.pop();
        if(cn==k) {
            answer=cnt;
            break;
        }

        cnt+=1;
        int pn = cn+1;
        int mn = cn-1;
        int dn = cn*2;


        if(pn>=0&&pn<=100000&&visited[pn]== false) {
            q.push({pn,cnt});
            visited[pn]= true;
        }
        if(mn>=0&&mn<=100000&&visited[mn]== false){
            q.push({mn,cnt});
            visited[mn]= true;
        }
        if(dn>=0&&dn<=100000&&visited[dn]== false){
            q.push({dn,cnt});
            visited[dn]= true;
        }
    }

    cout<<answer;
}

갈 수 있는 방법은 +1, -1, *2 이다.

bfs 이용한다. 현재 위치에서 3경우를 모두 계산해 {새로운위치, 경과시간}을 삽입한다.

visted 배열을 두어 이미 방문한 위치는 true로 한다. 만약 이미 방문한 위치라면 큐에 삽입하지 않는다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감