백준 / 숨바꼭질 / 1697번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 숨바꼭질 / 1697번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/1697

 

문제 설명

 

---

 

나의 풀이

 

def bfs(n, k):
    s = set() # 중복되는 값을 제거 해주는 역할을 가지고 있다.
    result = 0 # 카운트하는 방법을 사용할 것이다.

    s.add(n) # 초기 값을 부여한다.

    while s:
        new_s = set()
        for i in s:
            if k in s:
                return result
            if i + 1 <= k:
                new_s.add(i + 1)
            if i - 1 <= k and n - 1 > 0:
                new_s.add(i - 1)
            if i * 2 <= k:
                new_s.add(i * 2)
        result += 1
        s = new_s
    
    return -1

N, K = map(int, input().split())

print(bfs(N, K))

set()를 이용하여 중복되는 값을 제거하고 모든 경우의 수를 찾아서 카운트하는 방식을 사용했지만 시간 초과가 발생했다.

set()를 이용하여 중복되는 값을 제거를 했지만 다시 new_s를 통해서 s의 값을 초기화했을 때 이전에 탐색했던 값이 다시 들어갈 수 있는 문제가 생겼다.

그래서 이 방법은 값을 구할 순 있지만 시간이 초과할 수 밖에 없다는 방법을 알게되었다.

from collections import deque

def find(n, k):
    if n == k:
        return 0

    visited = set()
    queue = deque([(n, 0)])
    visited.add(n)

    while queue:
        current, result = queue.popleft()
        
        if current == k:
            return result
        
        next_positions = [current - 1, current + 1, current * 2]
        for next_pos in next_positions:
            if 0 <= next_pos <= 100000 and next_pos not in visited:
                visited.add(next_pos)
                queue.append((next_pos, result + 1))

    return -1  # 이 줄은 도달하지 않을 것입니다.

N, K = map(int, input().split())
print(find(N, K))

이 방법은 BFS 알고리즘을 사용하여 위에 있었던 기존에 있던 값이 다시 초기화되더라도 도달하지 않는 방법을 사용하기위해서 set()과 deqeu()를 사용하였다.

---

 

※ 알아야 할 것

 

https://newkimjiwon.tistory.com/113

Programmers / 숫자 변환하기 / Python

프로그래머스에 있는 이 문제랑 유사하다.