[백준 알고리즘 c++] 문제 42.숨박꼭질 1697

알고리즘

 

[문제]

 

문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

[나의 풀이]

문제
1. 수빈이가 동생을 찾을수 있는 가장 빠른 시간이 몇초후인지 구하시오.
입력
1. N과 K 좌표를 입력 받는다.
2. 100000 배열을 생성한다.
처리
3. 배열의 인덱스값에 이동 위치 + 1을 해준다.
출력

 

[소스 코드]

#include <iostream>
#include <queue>

int dx[3] = { -1,1,2 };
int N, K;
int check[100001] = { 0 };
bool isVisited[100001] = { false };

using namespace std;

int main()
{
	//
	// 문제
	// 1. 수빈이가 동생을 찾을수 있는 가장 빠른 시간이 몇초후인지 구하시오.
	// 입력
	// 1. N과 K 좌표를 입력 받는다.
	// 2. 100000 배열을 생성한다.
	// 처리
	// 3. 배열의 인덱스값에 이동 위치 + 1을 해준다.
	// 출력
	//
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> K;

	queue<int> que;
	que.push(N);
	isVisited[N] = true;

	while (!que.empty())
	{
		int x = que.front();
		que.pop();

		//이동방법은 3가지임
		for (int i = 0; i < 3; i++)
		{
			int nx = 0;

			if (dx[i] == 2)
			{
				nx = x * 2;
			}
			else
			{
				nx = x + dx[i];
			}
			
			if (nx >= 0 && nx <= 100000)
			{
				if (isVisited[nx] == false)
				{
					isVisited[nx] = true;
					check[nx] = check[x] + 1;
					que.push(nx);
				}
			}
		}
	}
	
	cout << check[K];

}

다익스트라 알고리즘을 참고해서 풀면된다.

다른 풀이)

#include <iostream>
#include <queue>
using namespace std;
int n, k;
bool visit[100001];
void bfs(int a){
    queue<pair<int, int>> q;
    q.push(make_pair(a, 0));
    while(!q.empty()){
        int x = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(x==k){
            cout << cnt;
            break;
        }
        if(x+1 >=0 && x+1<100001){
            if(!visit[x+1] ){
                visit[x + 1] = true;
                q.push(make_pair(x + 1, cnt + 1));
            }
        }
        if(x-1 >=0 && x-1<100001){
            if(!visit[x-1]){
                visit[x - 1] = true;
                q.push(make_pair(x - 1, cnt + 1));
            }
        }
        if(2*x >=0 && 2*x<100001){
            if(!visit[2*x]){
                visit[2*x] = true;
                q.push(make_pair(2 * x, cnt + 1));
            }
        } // 각 다음 좌표마다 q에 넣어준다.
    }
}
int main(){
    cin >> n >> k;
    visit[n] = true;
    bfs(n);
    return 0;
}

 

[피드백]