[코딩테스트 C++] 숨바꼭질

오늘의 문제

https://www.acmicpc.net/problem/1697

숨바꼭질

문제 분석

• 최대 입력은 100000이다. O(NlogN)인 알고리즘이면 충분하다.
• 각 지점마다 분기가 3개가 있으며, 원하는 지점까지 빨리 도착하는 시점을 출력해야한다.
• 그렇기 때문에 DFS가 아닌 BFS로 풀어야 넉넉하게 빠르게 풀 수 있다. 가까운 지점부터 검색하니까!

나의 풀이

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
const int MAX = 100000;
const int INF = 987654321;
int n, k;
int dx[] = {1, -1, 0};
bool visit[MAX+1] = {false, };

// 숨바꼭질
int bfs(){
    queue<pair<int, int>> q;
    q.push(make_pair(n, 0));
    visit[n] = true;
    while(!q.empty()){
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();
        dx[2] = num;
        for(int i=0;i<3;i++){
            int move = num + dx[i];
            if(move <0 || move > MAX)
                continue;
            if(move == k)
                return cnt+1;
            if(visit[move] == false){
                visit[move] = true;
                q.push(make_pair(move, cnt+1));
            }
        }
    }
    return 0;
}
int solution(){
    if(n == k)
        return 0;
    return bfs();
}

다른 답안

#include <stdio.h>
int min(int a,int b)
{
    if (a>b) return b;
    return a;
}
int find(int n,int k)
{
    if (n>k) return n-k;
    if (n==k) return 0;
    if (n==0) return find(n+1, k)+1;
    return min(min(find(n, k/2)+(k%2)+1,find(n, (k+1)/2)+(k%2)+1),k-n);
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    printf("%d\n",find(n,k));
}

배울 점

• 이사람은 dfs로 풀었다. 코드는 간단!