스파르탄 365 3주차 (5) 숨바꼭질

3주차

백준 1697번 랜선 자르기

문제링크 : https://www.acmicpc.net/problem/1697

💡 풀이 전 계획과 생각

• 갈 수 있는 위치를 모두 저장해서 가장 작은값을 구해보자
  -> ! 그래프를 그려서 생각하니 모두 저장할 필요가 없었다.
  
• 위치가 바뀔 때마다 정답에 1씩 추가해주면 되겠다.

💡 풀이

from collections import deque
import sys

input = sys.stdin.readline
subin, sister = map(int, input().split())

MAX = 100001
ans = [0] * MAX

def bfs():
    q = deque([subin])
    while q:
        now_pos = q.popleft()
        # print('now_pos: ', now_pos)
        if now_pos == sister:
            return ans[now_pos]
        for next_pos in (now_pos-1, now_pos+1, now_pos*2):
            # print('들어왔는지 확인')
            if 0<=next_pos<MAX and not ans[next_pos]:
                ans[next_pos] = ans[now_pos]+1
                q.append(next_pos)

print(bfs())

🧐 막혔던 점과 고민

• 그래프를 어떻게 구현할 것인가.

👏🏻 알게된 개념과 소감

• 그래프 구현 없이 반복문에서 그 다음 노드들을 쫙 탐색

 for next_pos in (now_pos-1, now_pos+1, now_pos*2):

• 누적하는 부분

ans[next_pos] = ans[now_pos]+1

• 정리하다 보니 미로 탐색과 너무 비슷한 문제였다.

🔥 해보고 싶은 것

[ __ ] 이번주에 풀어본 BFS / DFS 문제들과 코드를 다 뽑아서 비교후 나만의 방식을 확정해야겠다.