백준 1697 숨바꼭질

import sys
input = sys.stdin.readline
from collections import deque
from itertools import product

def find(a,b):
    q = deque()
    q.append(a)
    visited = [0]*100001

    if a == b:
        print("0")
        return 
    while q:
        k = []
        if visited[b] > 0:
            print(visited[b])
            return 
        temp = q.popleft()
        for j in [temp+1, temp-1, temp*2]:
            if j<100001 and visited[j] == 0 and j>=0:
                visited[j] = visited[temp]+1  
                q.append(j)

a ,b = map(int,input().split(" "))

find(a,b)

이 문제는 정말 눈물을 흘릴뻔했다😢 ㅠㅜㅠㅠ 제출만 최소 15번은 한 것 같다!

문제를 풀면서 배운 점은
1. 생길 수 있는 모든 상황을 다 처리해야한다
는 것이 가장 크다
처음에는 출발지와 도착지가 같은 경우의 수는 고려하지 못했다.
2. 조건을 걸어서 방문하지 않아도 되는 곳은 최대한 방문을 하지 말자

처음에는 카운팅 되는 수를 따로 배열에 저장하지 않고 덱속의 값을 한번 주르륵 다 처리하면 count++을 하는 방법으로 접근하였다. 하지만 이 방식으로 접근하니 메모리 에러가 계속 떴다.

visited 라는 배열을 두고 방문횟수를 저장하며 나아가는 방법을 택하니 방문한 곳은 다시 재방문 하지 않는다는 것이 보장되어 메모리가 줄어든 것 같다.