[알고리즘 / 백준] 13913 - 숨바꼭질 4

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

문제는 위와 같고, Deque 를 사용하여 BFS 를 구현하는데 최단 거리를 구할 수 있는 지점을 알아야 하므로 방문했는지 확인하는 visited 배열을 boolean 형식이 아닌 int 형으로 만들어서 해당 인덱스에 이전에 방문했던 위치값을 넣는 방식으로 구현하였습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
from collections import deque


def bfs(start):
    queue = deque()
    queue.append(start)  # 시작 위치를 deque 에 저장
    visited[start][0] = 0  # 시작 위치를 방문하는데 걸리는 시간 저장 (0)

	# 더 이상 이동할 지점이 없을 때까지 반복
    while deque:
        current = queue.popleft()

		# 현재 위치가 동생 위치와 같다면
        if current == k:
            return visited[current][0]  # 현재 위치까지 방문하는데 걸린 시간 반환

        for np in (current * 2, current + 1, current - 1):  # 이동할 수 있는 위치 순서대로 확인
            if 0 <= np < 100001 and visited[np][0] == -1:  # 다음 위치가 범위 내에 있고 다음 위치까지 이동하는데 걸린 시간이 -1 이면 아직 방문하지 않은 경우이므로
                visited[np][0] = visited[current][0] + 1  # 다음 위치로 이동하는데 걸린 시간 저장
                visited[np][1] = current  # 다음 위치로 이동하기 전에 방문한 위치 저장
                queue.append(np)  # deque 에 저장하여 BFS 수행


n, k = map(int, stdin.readline().split())
visited = [[-1, -1] for _ in range(100001)]  # [해당 인덱스까지 이동하는데 걸린 시간, 바로 이전에 방문했던 위치 인덱스]

print(bfs(n))  # 최단 시간 구하기

result = deque()  # 결과 배열 생성
result.append(k)  # 동생 위치 넣기
while visited[k][1] != -1:  # 바로 이전에 방문한 위치가 없을 때까지(-1, 즉 처음 위치일 때까지)
    result.appendleft(visited[k][1])  # 이전 방문 위치를 결과 배열 앞에 추가
    k = visited[k][1]

print(" ".join(map(str, result)))

 

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class BJAlgo_13913 {
    private static int n;
    private static int k;

    private static int[][] visited = new int[100001][2];  // [현재 위치까지 방문하는데 걸린 시간, 현재 위치를 방문하기 전 방문했던 위치 값] 저장

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

		// visited 배열 모든 값을 -1로 초기화
        for (int i = 0; i < 100001; i++) {
            Arrays.fill(visited[i], -1);
        }

        System.out.println(bfs(n));  // 최단 시간 구하기

        StringBuilder sb = new StringBuilder();
        sb.append(k);  // 가장 마지막 도착 위치 추가
        while (visited[k][1] != -1) {  // 이전에 방문한 위치가 없을 때까지 반복 (-1, 즉 시작 위치로 돌아올 때까지 반복)
            sb.insert(0, visited[k][1] + " ");  // 이전에 방문한 위치 값을 앞으로 추가
            k = visited[k][1];
        }

        System.out.println(sb);
    }

    private static int bfs(int start) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(start);
        visited[start][0] = 0;  // 처음 위치를 방문하는데 걸린 시간 0을 저장

		// 더 이상 이동할 위치가 없을 때까지 반복
        while (!deque.isEmpty()) {
            int current = deque.pollFirst();  // 앞에서 부터 확인할 위치 값 추출

			// 현 위치가 도착 위치와 같다면
            if (current == k) {
                return visited[current][0];  // 현 위치까지 오는데 걸린 시간 반환
            }

            for (int i = 0; i < 3; i++) {
                int next = move(i, current);  // 다음 위치 구하기

				// 다음 위치가 범위 내에 있고 다음 위치까지 방문하는데 걸린 시간이 -1 인 경우 아직 해당 위치를 방문하지 않은 경우이므로
                if (next >= 0 && next < 100001 && visited[next][0] == -1) {
                    visited[next][0] = visited[current][0] + 1;  // 다음 위치를 방문하는데 걸린 시간 저장
                    visited[next][1] = current;  // 다음 위치를 방문하기 이전에 방문한 위치를 저장
                    deque.add(next);  // BFS 수행을 위해 deque 에 다음 위치 저장
                }
            }
        }

        return -1;
    }

	// 다음으로 이동할 위치 값 반환
    private static int move(int idx, int c) {
        int result = -1;
        switch (idx) {
            case 0:
                result = c * 2;
                break;
            case 1:
                result = c + 1;
                break;
            case 2:
                result = c - 1;
                break;
        }

        return result;
    }
}