문제 출처 : https://www.acmicpc.net/problem/1697
사고과정
모든 경우를 다 진행시키면서 확인해봐야 결과를 도출할 수 있다. ( BRUTE FORCE 동시에 완전탐색 ) 그래서 그래프와 같이 탐색을 진행한다. 문제 과정 자체는 그냥 흘러가는 대로 풀면 된다. 다만 이제 생각한 것은 TIME과 같은 걸 접목할 때 어떤 방식을 취햐느냐 정도...
문제의 제한 조건에 대한 경우를 처리해줘야 한다. 그렇지 않으면 메모리나 시간에 대해서 지나치게 커질 수 있기 때문이다.
이 문제도 예외 처리를 해주지 않아서 메모리 초과가 떠 자꾸 틀린 케이스이다.
import sys
from collections import deque
N, K = list(map(int,sys.stdin.readline().rstrip("\n").split()))
time = 0
visit = {N}
subin = deque([(N,0)])
def bfs() :
while subin :
t = subin.popleft()
if t[0]==K :
return t[1]
next_s = {t[0]+1, t[0]-1, t[0]*2}
for n in next_s :
if n < 0 or n>100000:
continue
if not n in visit :
subin.append((n,t[1]+1))
visit.add(n)
print(bfs())다른 사람들은 조금 더 효율적인 방식을 취하였기에 한 번 공부해보자.
BFS를 이용한다는 점에서 알고리즘에 큰 차이는 없는 것 같다. 시간이 차이가 나는 건 사소한 조건들과 여러 예외처리 등을 통해 효율적인 결과를 낳는다.
방문 여부를 결정하기 위해 나는 visit 라는 set형식을 이용했다. 왜냐면 set은 검색에 걸리는 시간이 O(1)이니까. 하지만 다른 사람은 list형식을 이용하여 (dp처럼) 방문을 했다면 cache[방문] = time와 같은 방식을 사용했다. (limdongjin 님 풀이)
근데 이게 이렇게 시간 차이가 날 정도인가...?
같은 기능을 코드로 작성하더라도 작성하는 방법은 천차만별이다. 따라서 많이 짜보면서 그때그때 적합하다고 생각되는 구조로 작성할 줄 알아야 한다.
예를 들어 지금 그래프 탐색에서 HEIGHT의 책정 방식을 보면 처음에는 NODE의 개수를 일일이 저장하고 세면서 HEIGHT를 증가시켰다. 그 다음 방식은 튜플형식에 HEIGHT 자체를 저장하여 같이 움직이게 만들어줬다. 마지막 방식은 list에서 index를 이용하여 조회하며 HEIGHT의 값을 따로 저장하는 것이다. 이 밖에도 많은 방식이 있겠지만 여기서의 요점은 다양한 방식으로 구현하면서 내가 습득하여 이용할 줄 알아야 한다는 것이다.
효율성은 시간과 공간의 trade-off, 여기서는 공간을 이용하여 채택
