[백준] (bfs) 숨바꼭질 201031

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

1. 문제 풀이

 

2. 풀이 

 

 

 

 

 

 

from collections import deque
import sys

def solution(start, end):
    step = 0
    stack_list = deque([[start,step]])
    
    if start == end:
        return 0

    while stack_list:
        now_start, step = stack_list.popleft()

        x1 = now_start + 1
        x2 = now_start - 1
        x3 = now_start * 2

        if x1 == end or x2 == end or x3 == end:
            return step + 1

        stack_list.append([x1,step+1])
        stack_list.append([x2,step+1])
        stack_list.append([x3,step+1])

start, end = map(int, sys.stdin.readline().split())
print(solution(start, end))

 

- 문제점 1 : 중복되는 숫자들도 계속 deque 에 들어가서 리스트의 길이가 엄청 길어졌다.

- 문제점 2 : 범위 밖의 숫자는 안담는 조건도 포함해야했다. 

 

 

2) 수정 + 성공 

 

from collections import deque
import sys

def solution(start, end):
    step = 0
    stack_list = deque([[start,step]])
    history_set = set()

    if start == end:
        return 0

    while stack_list:
        now_start, step = stack_list.popleft()

        x1 = now_start + 1
        x2 = now_start - 1
        x3 = now_start * 2

        if x1 == end or x2 == end or x3 == end:
            return step+1

        if x1 not in history_set and x1 <= 100000:
            stack_list.append([x1,step+1])
            history_set.add(x1)

        if x2 not in history_set and x2 <= 100000:
            stack_list.append([x2,step+1])
            history_set.add(x2)

        if x3 not in history_set and x3 <= 100000:
            stack_list.append([x3,step+1])
            history_set.add(x3)


start, end = map(int, sys.stdin.readline().split())
print(solution(start, end))

 

- 문제점 1 해결 : historyset 을 만든 뒤에 이전에 가본적있는 숫자의 경우에는 deque_list에 담기지 않게 했다.

- 문제점 2 해결 : 범위 밖의 숫자도 담기지 않도록 조건문을 걸었다. 

 

 

 

 

3. 정리 - 프롬미투미  

분명 프로그래머스 테케만 돌렸더라면, 

합격이라 믿었을거임 

숫자 범위, 반례 계속 생각하면서 코드짜기