백준 1697번 숨바꼭질

문제 링크입니다: https://www.acmicpc.net/problem/1697

pair<int, int> 형 큐를 통해 first에는 위치를 second에는 경과시간을 저장하여 BFS 기법을 통해 문제를 해결했습니다.

한가지 주의할 점은 한번 도달한 지점은 다시 방문하지 않도록 visited 배열을 통해 도달여부를 파악하는 것입니다.

방문한 지점을 다시 큐에 넣을 경우 메모리 초과 발생과 함께 어마어마한 실행시간을 요구하기 때문에 문제를 풀 수 없습니다!

#include <iostream>

#include <queue>

using namespace std;

 

const int MAX = 100000 + 1;

bool visited[MAX];

 

int minSecond(int N, int K)

{

        queue<pair<int, int>> q;

 

        q.push(make_pair(N, 0));

        visited[N] = true;

 

        while (!q.empty())

        {

                 int curLoc = q.front().first;

                 int curSec = q.front().second;

                 q.pop();

 

                 if (curLoc == K) //목적지 도달 시 break

                         return curSec;

 

                 //세 가지 경우의 수

                 //이미 방문한 지점은 큐에 넣지 않는다

                 if (curLoc + 1 < MAX && !visited[curLoc + 1])

                 {

                         q.push(make_pair(curLoc + 1, curSec + 1));

                         visited[curLoc + 1] = true;

                 }

                 if (curLoc - 1 >= 0 && !visited[curLoc - 1])

                 {

                         q.push(make_pair(curLoc - 1, curSec + 1));

                         visited[curLoc - 1] = true;

                 }

                 if (curLoc * 2 < MAX && !visited[curLoc * 2])

                 {

                         q.push(make_pair(curLoc * 2, curSec + 1));

                         visited[curLoc * 2] = true;

                 }

        }

}

 

int main(void)

{

        int N, K;

        cin >> N >> K;

 

        cout << minSecond(N, K) << "\n";

 

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~