[BOJ/백준] 12851 숨바꼭질 2

# 12851 숨바꼭질

N,M = map(int,input().split())
dp = [-1]*100001
if M != N:
    stack = [(N,0,'')]
    flag = False
    result = float('inf')
    dire = ['M','P','T']
    total = set()
    visited = set()
    while stack:
        X,time,how = stack.pop(0)
        if time > result:
            break
        temp =  [X-1,X+1,X*2]
        for ind,k in enumerate(temp):
            if 0<=k<=100000 and time+1<=result:
                if dp[k] == -1 or dp[k] == time+1:
                    dp[k] = time+1
                    stack.append((k,time+1,how+dire[ind]))
                    if k == M:
                        result = time+1
                        total.add(how+dire[ind])

        
    print(result)
    print(len(total))
else:
    print(0)
    print(1)

처음에는 단순히 BFS처럼 풀어주었다.  결과값인 result를 큰 수로 설정해놓고, BFS를 하면, 최초로 변하는 값이 제일 작은 값이 되고, 출력되어야하는 값이 되니, result값보다 작은 time일때만 들어오게 설정해주었다. 그리고, 이 문제에서 처음에 틀렸던 이유 중 하나가, 같은 시간대에 정답에 올 수 있는 경우의 수가 많았다. 그래서 방문표시를 해주는 dp를 최초 방문이거나 아니면 time+1과 같을때, 같은시간대일때만 올 수 있도록 해줬다. 

 또한 전체적인 방법의 수를 찾기 위해, 이동방향을 저장해주는 로직을 추가해줬었다. 그래서 목표값 M에 도착을 하면, total에 추가를 해줘서, 전체 방법의 가지수를 찾아냈다.

 

하지만 이 방식의 문제점은, 시간이 오래걸린다는 점이다. 매번 BFS를 하는것과 같고, 그럼으로서 시간이 느릴수 밖에 없었다.

 

 

welog.tistory.com/61에서 풀었던 이모티콘 문제와 비슷한 방식으로 하면 된다. 문제 : www.acmicpc.net/problem/14226

14226번: 이모티콘

이와 같은 문제는 BFS이기도 하지만, 각각의 BFS를 하는것보다, 한 타임씩 맞춰서 한꺼번에 하는 편이 시간을 절약하는데 도움이 되는 것 같다.

 

# 12851 숨바꼭질

N,M = map(int,input().split())
times = 0
ways = 0
prev_vistied = {N : 1}
visited = [True]*100001
if N == M:
    ways = 1
while not ways:
    new_visited = {}
    for number in prev_vistied:
        for new_number in [number-1,number+1,2*number]:
            if 0<= new_number <= 100000 and visited[new_number]:
                if new_number == M:
                    ways += prev_vistied[number]
                else:
                    if new_visited.get(new_number):
                        new_visited[new_number] += prev_vistied[number]
                    else:
                        new_visited[new_number] = prev_vistied[number]
    for visited_number in new_visited:
        visited[visited_number] = False
    prev_vistied = new_visited
    times += 1 

print(times)
print(ways)

개선한 방식은 다음과 같다. 

직전에 방문한 지점 prev_visited를 반복문을 돌리고, 방문하지 않았으면, new_visited에 prev_visited에서 누적된 해당 number에 올 수 있는 방법의 가지수를 더해주면 된다.

 

한번의 반복문이 끝나고 난뒤에, visited 함수에 방문을 한 것을 표시해주고, prev_visted를 new_visited로 변경시켜주면 된다.

 

이렇게 하면, 위의 BFS는 각각의 방법 하나하나마다 결과값에 도착할때까지 BFS를 하면서 반복문을 돌려야하지만, 이 방법은 number 단위로 해당 number에 올 수 있는 최소 타임을 이용해 한꺼번에, BFS를 한다는 점이다.

 

위와 같은 time을 세는 문제 같은 경우엔 일반적인 BFS가 아닌, 한 타임별로 전체를 반복문 돌리는 풀이방식도 생각해봐야겠다.