일반적인 숨바꼭질 문제

숨바꼭질 4

문제

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

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

입력

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

출력

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

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

 

예제 입력 1 

5 17

예제 출력 1 

4

5 10 9 18 17

 

예제 입력 2 

5 17

예제 출력 2 

4

5 4 8 16 17

 

위 문제는 bfs를 통해서 풀 수 있는 문제 중의 하나이다. 

예를 들어 수빈이는 4 동생은 17의 위치에 있다면, 수빈은 1초 마다 x + 1, x -1, x * 2 이 세 가지 경우 중 하나로 이동하면서 가장 빠르게 찾을 때의 경우를 찾으면 된다.

 

4

3     5     8 

2 4 6  4 6 10  7 9 16 

 ..........                 15  17 

이런식으로 회차를 넘길 때 마다 여러가지 경우의 수가 나오고 여기서 답이 있는지 없는지 확인한 뒤 답을 찾아내면 정답이 완성된다. 보통 일반적으로 해당 알고리즘 문제는 

def bfs(N, K) :
    dist = [0] * 100001
    move = [0] * 100001
    deq = deque()
    deq.append(N)
    ans = []
    while deq :
        x = deq.popleft()
        if x == K :
            while x != N :
                ans.append(x)
                x = move[x]
            ans.append(N)
            ans.reverse()
            break
        else :
            for i in (x + 1, x - 1, x*2) :
                if 0<= i <= 100000 and dist[i] == 0 :
                    dist[i] = dist[x] + 1
                    move[i] = x
                    deq.append(i)
    return ans

이런 식으로 사용해서 풀면 된다. 그러나 우리는 함수형으로 문제를 풀 것이다. 여기서 한걸음 더 나아가 보자

일단 해당 식을 쓰기 위해서는 중심이 되는 while 문을 변환 시켜야 한다. 

 

While 을 함수형으로 표현하기 

우선 while을 lambda로 표현해 보기 전에 람다식을 바로 사용할 수 있게 해주는 (lambda  ~ ) (x)를 한번 보자

(lambda  ~ ) (x)의 뜻은 왼쪽 lambda 식에 오른쪽 (x) 값을 즉시 적용한다는 뜻이다. 

print ( (lambda x : x + 5) (4) )
'''
9
'''

즉 위의 보이는 것 처럼 람다식이 바로 적용 되었다는 것을 확인할 수 있다. 

 

이제 while 문을 lambda로 표현한 것을 살펴보자. 

fp_while = lambda pred, fun, acc \
    : (lambda val: fp_while(pred, fun, val) if pred(val) else val)  ( fun(acc) )

처음 보면 어려울 수 있다. 코드를 살펴 보면  pred, fun, acc 가 각각 들어 오면 

(lambda val: fp_while(pred, fun, val) if pred(val) else val)  ( fun(acc) ) 를 실행하게 된다. 일단 직접 사용해보면 어떤식으로 동작하는지 살펴 보자 

fp_while = lambda pred, fun, acc \
    : (lambda val: fp_while(pred, fun, val) if pred(val) else val)  ( fun(acc) )

def condition(x) :
    print ( 'condition' , x )
    if x < 3 :
        return True
    return False

def add_one(x) :
    print ( 'add_one' , x )
    return x + 1


print ( fp_while( condition, add_one, 1) ) 
'''
add_one 1
condition 2
add_one 2
condition 3
3
'''

지금 condition이라는 함수와 add_one이라는 함수를 만들어 위의 while문에 적용해 보았다. 결과를 살펴보면 
fun(acc) -> add_one이 먼저 동작하고 그 후에 condition 함수가 적용 되었다는 것을 확인 할 수 있다. 이를 보기 좋게 일반적을 함수로 표현하면 

def fp_while( pred, fun, acc) :
    val = fun(acc)
    if pred(val) :
        return fp_while(pred, fun, val) 
    return val

다음 처럼 간단하게 표현 할 수 있다. 이제 이를 활용하여 위의 숨바꼭질 문제를 풀어보자 

N, K = 4, 17
dist = [0] * 100001
move = [0] * 100001
deq = deque()
ans = []

def bfs() :
    global deq 
    deq.append(4)
    go (
        deq,
        fp_while( lambda x : True if x else False)( loop_check )
    )

def loop_check(deq) :
    global dist, move, N, K, ans
    x = deq.popleft()
    if x == K :
        while x != N :
            ans.append(x)
            x = move[x]
        ans.append(N)
        ans.reverse()
        deq = 0
    else :
        go (
                [ x + 1, x - 1, x*2],
                filter( lambda x :  0<= x <= 100000 and dist[x] == 0 ),
                update(x),
            )
    return deq 

@curry
def update(x, iterable) :
    global  dist, move, deq
    for acc in iterable :
        dist[acc] = dist[x] + 1
        move[acc] = x
        deq.append(acc)
    return 
    
bfs()
print(ans)

지금 fp_while을 이용해 코드를 풀었지만;;; 생각보다 엄청 코드도 길어지고 굉장히 불편해 보이는 코드가 되었다.... 

함수형 프로그래밍을 bfs 도입하는건 그리 좋지 못한 생각이였나 보다.. 조금 더 다듬고 생각해보아야할 필요성이 크게 느껴진다.