[백준] 1697번 숨바꼭질 - (Python)

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

1697번: 숨바꼭질

알고리즘 분류 힌트가 없었다면, 접근법을 찾기 굉장히 어려웠었던 문제. 

BFS를 통해 접근해야 합니다. 각 위치에서의 +1, -1, x2 값을 노드로 계속해서 진행한 뒤, 해당 노드가 찾고자 하는 K값이라면, 종료시키면 됩니다. 또 해당 노드의 범위가 0에서 100,000 사이의 범위에서만 존재해야 하므로, 이 부분 역시 참고해줘서 문제를 해결하면 됩니다.

※ 고려사항

1. 횟수 카운팅

2. BFS 구현

---

1. 횟수 카운팅

먼저 최단시간을 저장할 리스트가 필요합니다. BFS를 통해서 구현해야 하므로, 각 노드별 list가 필요로 되는데 해당 노드의 범위는 문제에서 0 ~ 100,000 사이의 값을 가집니다. 즉, 100,001 개의 노드가 필요로 됩니다. 

각 노드를 0으로 초기화 시킨 뒤, 각 노드를 +1, -1, x 2, 한 노드로 만들어줍니다. 이때 변경된 노드는 이전에 방문되지 않은 노드여야 합니다. 왜냐하면 이미 방문되었다는 말은 해당 노드까지 더 짧은 루트가 존재한다는 의미이기때문에, 해당위치에서는 더 이상 순간이동 혹은 이동을 해서는 안됩니다. 

따라서 너비우선으로 계속해서 진행하면서, 이미 방문한 노드라면, 해당노드에서는 이동을 멈추어 목표한 K노드에 도달할 때까지 반복합니다. BFS 설명에서 구현설명까지 하겠습니다.

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())

# 걸린시간 리스트
visit = [0 for _ in range(100001)]

 

2. BFS 구현

해당 문제는 너비우선탐색으로 BFS방식으로 구현해야 합니다. 따라서 Queue를 이용하여 구현하게 됩니다.

다만 구현을 할 때, 해당 노드가 K와 일치하는지, 그렇지 않다면 해당 범위내에 존재하면서 방문되지 않았는지 유무를 판단해야 합니다. 해당 내용의 설명은 횟수 카운팅 내용의 방식과 동일합니다. 따라서 코드로 구현하면 다음과 같습니다.

def bfs(n):
    # 큐 생성
    q = deque()
    q.append(n)

    # 시작위치 1 표시
    visit[n] = 1

    while q:
        # 큐에서 원소 pop
        c = q.popleft()

        # k와 같다면 -1 하고 출력 -> 시작을 1로 했기 때문
        if c == k:
            print(visit[c] - 1)
            return
        
        # 순간이동, 일반이동 고려
        for i in (c-1, c+1, c*2):

            # 범위내에 있다면, 해당노드 걸린시간 +1
            if 0 <= i <= 100000 and not visit[i]:
                visit[i] = visit[c] + 1
                q.append(i)

---

전체코드

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())

# 걸린시간 리스트
visit = [0 for _ in range(100001)]

def bfs(n):
    # 큐 생성
    q = deque()
    q.append(n)

    # 시작위치 1 표시
    visit[n] = 1

    while q:
        # 큐에서 원소 pop
        c = q.popleft()

        # k와 같다면 -1 하고 출력 -> 시작을 1로 했기 때문
        if c == k:
            print(visit[c] - 1)
            return
        
        # 순간이동, 일반이동 고려
        for i in (c-1, c+1, c*2):

            # 범위내에 있다면, 해당노드 걸린시간 +1
            if 0 <= i <= 100000 and not visit[i]:
                visit[i] = visit[c] + 1
                q.append(i)
bfs(n)

---

해당문제는 BFS임을 알고 접근하면, 구현방식을 보다 쉽게 찾을 수 있습니다. 저도 그래프문제를 많이 풀어보지 못했지만, 자주 연습하다 보니, 구현방식을 떠올리는데 큰 어려움을 없었습니다. DFS, BFS는 확실히 많은 문제를 통해 다양한 학습을 하는 것이 실력향상에 도움을 주는 것 같습니다.

설명의 오류나, 궁금하신점은 언제든 피드백 해주시면 감사하겠습니다 ^~^