백준 : 1679번, 숨바꼭질

문제 주소 : www.acmicpc.net/problem/1679

정답 비율 : 24.961% (2021.02.15 16:44 기준)

1679번: 숫자놀이

문제 요약 :

순서대로 숫자 N, K가 주어집니다. N에 대하여 다음과 같이 3가지 행동 중 하나를 선택하여 진행합니다.

1. N = N x 2

2. N = N - 1

3. N = N + 1

 

이때 N이 K 되기 위하여 최소 몇 번 행동해야 합니까?

 

EX) N = 5, K = 17 => 답 : 4

5 = x2 => 10 = -1 => 9 = x2 => 18 = -1 => 17

 

문제 조건 :

입력 : N과 K가 차례대로 주어집니다. (범위 : 0 이상 100,000 이하)

출력 : 최소 행동 수

시간 : 2 초

 

문제 풀이 :

BFS문제입니다. 큐를 사용하여 구현하였습니다. 문제를 정리하면 다음과 같습니다.

 

1) enqueue 조건 : 처음 입력받은 N, N에 대하여 행동 후에 값이 0 ~ 100000 사이 값일 때, 중복 값이 아닐 때

2) dequeue 조건 : X

3) N > K 일 때 할 수 있는 행동은 N - 1입니다.

4) BFS에서 종료의 조건은 queue가 비어있거나, 현재 행동한 횟수가 이전에 구한 최소 행동 횟수보다 큰 경우입니다.

 

enqueue에서 중복 값 제외 이유

BFS로 탐색을 진행하므로 두 번째 또는 n 번째 방문하는 곳은 첫 번째 방문보다 무조건 많은 행동을 한 경우입니다. 따라서 제외합니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int visit[100001];
int cque[100001];
int front = 0, rear = 0;

void enque(int n)
{
	cque[rear++] = n;
}

int deque(void)
{
	return cque[front++];
}

int main(void)
{
    int N, K, i = -1;
    scanf("%d %d", &N, &K);
    
    if(N >= K)
    	visit[K] = N - K;
    else
    {
    	enque(N);
    	visit[N] = 1;
    	visit[K] = K - N;
    	
    	int c = 0;
    	while(front != rear)
    	{
    		int tmp = deque();
    		int arr[3] = {tmp - 1, tmp + 1, tmp * 2};
    		
    		if(visit[tmp] >= visit[K])
    			break;
    		
    		for(i = 0; i < 3; i++)
    		{
    			if(arr[i] >= K && visit[tmp] + arr[i] - K < visit[K])
    			{
    				visit[K] = visit[tmp] + arr[i] - K;
				}
    			else if(arr[i] >=0 && arr[i] <= 100000 && !visit[arr[i]])
    			{
    				enque(arr[i]);
    				visit[arr[i]] = visit[tmp] + 1;
				}
			}
		}
    }
    printf("%d", visit[K]);
    
    return 0;
}

 

-> 우선 큐를 대충 구현하였습니다. 다행히도 문제를 해결 함에 있어서 큐의 크기가 부족하진 않았습니다.

-> visit은 방문을 검증하는 동시에 몇 번째 행동에서 방문한 것인지를 저장합니다.

 

Python3

#solve 1697  
import sys  
sys.setrecursionlimit(10**8)

n, k = list(map(int, input().split()))
que = [[n, 0]]

if n >= k:
    print(n-k)
else:
    visit = [0 for i in range(100001)]
    visit[k] = k - n
    
    while que:
        tmp = que.pop(0)
        
        if tmp[1] > visit[k]:
            break
        
        if tmp[0] >= k and tmp[1] + tmp[0] - k < visit[k]:
            visit[k] = tmp[1] + tmp[0] - k
            continue
            
        if tmp[0] < 0 or tmp[0] > 100000 or visit[tmp[0]]:
            continue
        
        visit[tmp[0]] = 1
        
        que.append([tmp[0] * 2, tmp[1] + 1])        
        que.append([tmp[0] + 1, tmp[1] + 1])
        que.append([tmp[0] - 1, tmp[1] + 1])

    print(visit[k])
        

 

-> python으로는 queue에 값과 몇 번째 행동인지를 저장하였습니다.

 

 

***

다른 사람의 코드 길이를 보니 170B ~ 500B 이길래 코드를 확인하니 재귀 함수로 풀었습니다. N에서 K로 가는 것이 아니라 역으로 K에서 N으로 가는 것이었습니다. 정말 멋진 코드이었습니다.

 

추가로 다음 코드는 실패한 코드이지만 재미로 작성해보았습니다. DFS + 함수 포인터 배열

#include<stdio.h>

#define ABS(x) x < 0 ? x * -1 : x

int P_1(int a)
{
	return a + 1;
}
int P_2(int a)
{
	return a * 2;
}
int P_3(int a)
{
	return a - 1;
}
int P_4(int a)
{
	return a / 2;
}

int (*fp[4])(int) = {P_1, P_2, P_3, P_4};

void dfs(int N, int K, int *min, int count)
{
	if(count > *min)
		return;
	else
	{
		if (N == K)
			*min = count;
		else
		{
			int i = -1;
			for (i = 0; i < 3; i++)
			{
				N = fp[i](N);
				dfs(N, K, min, count + 1);
				N = fp[(i + 2) % 4](N);
			}
		}
	}
}

int main(void)
{
    int N, K, min = -1;
    scanf("%d %d", &N, &K);
    
    min = ABS(N - K);
    
    if(N >= K)
    	printf("%d", min);
    else
    {
    	dfs(N, K, &min, 0);
    	printf("%d", min);
    }
    return 0;
}

 

-> 배열을 사용해도 무관하지만 함수 포인터를 사용해보고 싶었습니다. ㅎㅎ