91. 백준 1697 번 파이썬 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 BOJ 1697 번 숨바꼭질 입니다.

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

백준 1439 번 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

from collections import deque
N, K = map(int, input().split())
graph = [0 for _ in range(200000)]

def isVaild(x):
    if 0 <= x < 200000 and graph[x] == 0:
        return True
    return False

def BFS(N):
    queue = deque()
    queue.append(N)
    while queue:
        x = queue.popleft()

        if x == K:
            print(graph[x])
            break

        if isVaild(x + 1):
            queue.append(x + 1)
            graph[x + 1] = graph[x] + 1

        if isVaild(x - 1):
            queue.append(x - 1)
            graph[x - 1] = graph[x] + 1

        if isVaild(x * 2):
            queue.append(x * 2)
            graph[x * 2] = graph[x] + 1

BFS(N)

 

문제 요약

일차원 선분 안에서 수빈이가 동생을 찾는 문제입니다.

수빈이는 점 x를 기준으로 x+1 or x-1 or x*2 의 좌표로 이동가능하고, 한번 이동시마다 1초가 걸립니다.

이때 수빈이가 동생을 찾는데 걸리는 최소한의 시간을 출력하는 문제입니다.  

 

문제 접근

최단거리, 최소시간은 보통 BFS를 이용하면 문제 풀기 좋습니다.

현재 위치가 x라면 x + 1, x  - 1, x * 2 가 방문가능한지 살피고, queue에 넣습니다.

queue에 넣음과 동시에 x좌표로 이동하기까지 걸린 시간을 가져와

다음 이동시간을 계산해서 저장합니다.

x 좌표까지 이동 시간 + 1초

이를 동생을 찾을 때 까지 반복하고, 동생을 찾으면 계산한 이동시간을 출력하면 됩니다.

 

파이썬 코드 구현

위의 직관을 이용하여 코드를 구현 해봅시다. BFS를 이용합니다.

 

먼저 수빈이의 위치, 동생의 위치인 N, K를 입력받고

1차원 직선을 표현하기 위해 리스트를 생성합니다.

수빈이가, 동생의 최대 위치보다 큰 범위로 이동할 수 있기 때문에 크게 잡아줬습니다. (수빈이 현재 위치 * 2로 이동 가능)

from collections import deque
N, K = map(int, input().split())
graph = [0 for _ in range(200000)]

 

어떤 좌표가 들어오면 해당 좌표가 방문 가능한지 확인해주는 함수 isVaild를 구현합니다.

좌표가 그래프 범위를 벗어나지 않는지, 이미 방문한적은 없는지 판단하는 함수입니다. 

def isVaild(x):
    if 0 <= x < 200000 and graph[x] == 0:
        return True
    return False

 

BFS를 queue를 이용해 구현합니다.

좌표 x + 1, x -1, x * 2 가 방문 가능하다면, x좌표로 이동하기 까지 걸린 시간 + 1 초를 계산해 저장하고

다음번에 이동할 좌표를 queue에 넣어줍니다.

만약 방문한 좌표가 동생의 위치랑 같다면 탐색을 중지하고 걸린 시간을 출력합니다. ( if  x == K ) 

def BFS(N):
    queue = deque()
    queue.append(N)
    while queue:
        x = queue.popleft()

        if x == K:
            print(graph[x])
            break

        if isVaild(x + 1):
            queue.append(x + 1)
            graph[x + 1] = graph[x] + 1

        if isVaild(x - 1):
            queue.append(x - 1)
            graph[x - 1] = graph[x] + 1

        if isVaild(x * 2):
            queue.append(x * 2)
            graph[x * 2] = graph[x] + 1

 

이제 수빈이의 위치를 시작으로 구현한 BFS 함수를 실행시키면 됩니다.

BFS(N)

 

백준 1697 번 숨바꼭질 파이썬 최종 코드입니다.

from collections import deque
N, K = map(int, input().split())
graph = [0 for _ in range(200000)]

def isVaild(x):
    if 0 <= x < 200000 and graph[x] == 0:
        return True
    return False

def BFS(N):
    queue = deque()
    queue.append(N)
    while queue:
        x = queue.popleft()

        if x == K:
            print(graph[x])
            break

        if isVaild(x + 1):
            queue.append(x + 1)
            graph[x + 1] = graph[x] + 1

        if isVaild(x - 1):
            queue.append(x - 1)
            graph[x - 1] = graph[x] + 1

        if isVaild(x * 2):
            queue.append(x * 2)
            graph[x * 2] = graph[x] + 1

BFS(N)

 

백준 1697 번 숨바꼭질 자세한 설명 및 파이썬 코드였습니다.

감사합니다.