[백준 - Python] 1697. 숨바꼭질 (DFS/BFS)

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

1697번: 숨바꼭질

 

코드

from collections import deque

n, k = map(int, input().split())
max_num = 100000
visited = [0] * (max_num + 1)

def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        if x == k:
            print(visited[x])
            break

        for j in (x-1, x+1, x*2):  # 반복문에서 튜플 사용
            if j < 0 or j > max_num:
                continue
            if not visited[j]:  # 파이썬에서 0만 False, 나머지 정수는 True
                visited[j] = visited[x] + 1
                queue.append(j)

bfs()

 

문제를 처음 읽고, 이게 왜 DFS/BFS 문제인지 의아했다.

뭔가 그리디 문제 같다는 생각을 했던 것 같다.

 

BFS를 활용해 푸는 문제였다.

문제는 단순했지만, 처음 접해보는 문제 유형이라 데이터로 잘 기억해 두어야 겠다.

 

BFS로 풀어야겠다는 생각을 했으면 문제 풀이 자체는 많이 어렵지는 않다고 생각한다.

 

4방향 혹은 8 방향으로 이어진 연결 요소를 구하는 문제에서

방향 리스트를 따로 설정해서 4 혹은 8의 범위를 갖는 반복문을 돌린 것과 비슷하지만

이 문제에서는 가능한 3가지 경우에 대해서

튜플을 그대로 반복문에 넣어서 구현했다.

(해당 방식을 기억해 두면 나중에 유용하게 활용할 수 있을 것 같다.)

 

또한, visited 리스트를

해당 숫자까지 도달하는데 걸리는 시간을 저장하는 변수로 활용했다는 점도

이 문제의 주요한 해결 포인트였던 것 같다.

 

파이썬에서

0을 제외한 나머지 모든 정수들은 True값을 갖고,

0은 False값을 갖는다.

이 점을 활용한 코드였다.

 

 

---

 

 

[문제 특징 별 DFS와 BFS의 활용]

 

1. 그래프의 모든 정점을 방문하는 것이 핵심인 문제 ( DFS, BFS )

단순히 모든 정점을 방문하는 것이 문제의 핵심이라면 DFS, BFS 두 방법 중 어느 것을 사용해도 상관이 없다.

 

2. 경로의 특징을 저장해야 하는 문제 ( DFS )

각 정점에 숫자가 적혀 있고 a부터 b로 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 조건이 있거나,

경로에 가중치가 있다거나, 이동 과정에서 제약이 있는 등의

각각의 경로마다 특징을 저장해둬야 하는 문제는 DFS를 사용한다.

(BFS는 경로의 특징을 가지지 못한다.)

 

3. 최단 거리를 구하는 문제 ( BFS )

DFS로 경로를 탐색할 경우에는 처음 발견되는 해답이 최단 거리가 아닐 수 있지만,

BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 나오는 해답이 곧 최단 거리가 된다.

예를 들면, 미로 찾기 등의 문제가 있다.

 

4. 기타

검색 대상 그래프의 크기가 정말 크다면 DFS를 고려하고,

검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 고려해보면 좋다.