[#13549] 숨바꼭질 3

RookieAND·2022년 11월 26일

BFS 백준 코테

BaekJoon

목록 보기

36/42

❓ Question

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

📖 Before Start

BFS 알고리즘을 사용하였으나, 약간의 발상 전환이 필요하다.

이번 문제는 BFS 탐색 알고리즘을 활용한 그래프 탐색 문제였다.
간만에 풀어보는 그래프 탐색 문제인지라 꽤 긴장했다. 다 까먹었을까봐..

✒️ Design Algorithm

순간이동은 0초가 걸리므로, 이를 먼저 고려하여 시간을 체크하자.

0부터 100,000 까지 존재하는 1차원 공간 내부에 점 N 과 K 가 있다.
수빈이가 위치한 N 좌표에서 동생이 위치한 좌표 K 까지 이동을 해야 하는데,
총 세 가지 방식 (N - 1, N + 1, N * 2) 으로 좌표 이동이 가능하다고 한다.

단, 순간이동 (N * 2) 의 경우 0초가 걸리며, 나머지 이동은 각각 1초가 걸린다.
여기까지 문제를 읽고 느낀 점은, "순간이동을 먼저 고려하여 탐색을 해보자" 였다.

💻 Making Own Code

✅ Correct Code

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
visited = [-1] * 100001

def bfs(start):
    visited[start] = 0
    queue = deque([start])
    while queue:
        current = queue.popleft()
        if current == K:
            return visited[K]
        # x 2 배는 시간을 잡아먹지 않으므로, 먼저 체크해야 함.
        nd = current * 2
        if 0 <= nd <= 100000:
            # 만약 기존의 경로보다 새로운 경로의 시간이 더 작을 경우에만 업데이트 진행.
            if visited[nd] == -1 or (visited[nd] != -1 and visited[nd] > visited[current]):
                visited[nd] = visited[current]
                queue.append(nd)
        # 앞 뒤로 1 칸씩 움직이는 경우를 고려하여 체크.
        for nd in [current - 1, current + 1]:
            if 0 <= nd <= 100000:
                # 만약 기존의 경로보다 새로운 경로의 시간이 더 작을 경우에만 업데이트 진행.
                # 한번도 방문하지 않은 좌표의 경우에도 업데이트가 필요하기에 추가 조건 발행.
                if visited[nd] == -1 or (visited[nd] != -1 and visited[nd] > visited[current] + 1):
                    visited[nd] = visited[current] + 1
                    queue.append(nd)

print(bfs(N))

BFS 탐색을 이용하되, 소요 시간을 업데이트 하는 조건을 추가했다.

현재 좌표에서 다음 좌표로 탐색을 진행하되, 소요 시간을 업데이트하는 조건을 지정했다.

이동한 좌표가 아직 한번도 방문하지 않은 곳일 경우.
이동한 좌표까지 걸리는 소요 시간보다, 현재 업데이트 할 소요 시간이 적은 경우

하지만 막상 코드를 보니 너무 불필요한 조건이 덕지덕지 발라진 느낌이라 아쉬웠다.
따라서 정답 처리를 받은 후 다른 분들의 코드를 보다, 눈이 번뜩이는 풀이를 보았다.

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
visited = [-1] * 100001

def bfs(start):
    visited[start] = 0
    queue = deque([start])
    while queue:
        current = queue.popleft()
        if current == K:
            break
        for nd in [current * 2, current - 1, current + 1]:
            if 0 <= nd <= 100000 and visited[nd] == -1:
            	# 순간 이동의 경우 deque 앞에 값을 추가하여 우선 연산 진행.
                if nd == current * 2:
                    visited[nd] = visited[current]
                    queue.appendleft(nd)
                # 일반 이동의 경우 deque 뒤에 값을 추가하여 후순위 연산 진행.
                else:
                    visited[nd] = visited[current] + 1
                    queue.append(nd)
    return visited[K]

print(bfs(N))