[1697] 숨바꼭질

 

숨바꼭질 성공출처다국어분류

한국어   

 Silver I
너비 우선 탐색그래프 이론그래프 탐색
난이도 제공: solved.ac — 난이도 투표하러 가기

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

89431

24746

15388

24.825%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

 

숨바꼭질 문제 중 가장 쉬운 문제

처음에 bfs를 활용하고자 했는데 메모리를 생각 안하고 전부 append 시켜서 메모리 초과가 났습니다.ㅋㅋㅋㅋ

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
count = 0
d = deque()


def bfs():
    global count
    d.append(n)
    while d:
        x = d.popleft()
        if x == m:
            break
        d.append(x - 1)
        d.append(x + 1)
        d.append(x * 2)
        count += 1


bfs()
result = 0
while count != 0:
    count = count // 3
    result += 1
print(result)

 

그래서 append를 할 때 조건을 넣어줬습니다!

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
count = 0
d = deque()
visit = [0] * 100001


def bfs():
    d.append(n)
    while d:
        x = d.popleft()
        if x == m:
            return visit[x]
        check(x - 1, x)
        check(x + 1, x)
        check(x * 2, x)


def check(nex, cur):
    if 100001 > nex >= 0 and (visit[nex] == 0 or visit[cur] + 1 < visit[nex]):
        visit[nex] = visit[cur] + 1
        d.append(nex)


print(bfs())

 

일단 코드량을 줄이기 위해서 check 함수를 따로 만들었습니다.

nex는 다음 값을 나타내는 변수이며 x - 1, x + 1, x * 2 를 나타냅니다.

cur은 현재 값을 나타내며 덱에서 popleft() 한 값을 나타냅니다.

cur의 값을 popleft()하여 큐와 같은 형태로 bfs를 구현해주고, 이 값을 check 함수에 각 계산해야 되는 값으로 nex 매개변수에 넣어줍니다.

check 함수에서는 nex의 범위를 산정해주고, visit 배열에 내가 지나온 방의 수를 저장해줍니다.

내가 다음 방문할 방의 갯수가 0개이면 이전 기록이 없으므로 방문합니다.

혹은 내가 지금까지 방문한 방의 갯수 + 1보다 다음에 방문할 방에 기록된 갯수가 더 크다면

지금 방을 찾는 횟수가 이전에 방을 찾은 횟수보다 더 작다는 의미므로 visit[nex]의 값에 현재 횟수 + 1을 덮어 씌운 후 d.append(nex)를 해줍니다.