[백준 알고리즘] 13549번 숨바꼭질 3(Java) 문제 풀이

문제

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

13549번: 숨바꼭질 3

어떻게 풀 것인가?

처음에는 DP를 생각했다. 하지만 문제를 계속해서 틀렸고, 생각의 흐름을 바꿨다.

그래프를 이용한 BFS 문제였다.

다만 인접행렬이 아닌 일차원 배열 형태의 입접리스트로 풀어야했다.

BFS를 이용

visit과 timezone이라는 배열을 생성이후에 100,000이라는 범위에서 시간과 방문형태를 계속 계산한다. 그리고 큐가 전부 비워지면 timezone에 해당 목적지를 저장한 값이 저장이었다.

풀면서 놓쳤던점

처음 문제 접근법이 잘못되었다. 최근에는 문제를 랜덤으로 풀고있는데 계속 BFS문제만 풀게 되는 것 같다...

이 문제를 통해 얻어갈 것

BFS의 활용

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

// 백준알고리즘 13549 숨바꼭질 3

public class Main {
    static int me, brother;
    static boolean[] visit;
    static int[] timezone;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        me = Integer.parseInt(st.nextToken());
        brother = Integer.parseInt(st.nextToken());
        visit = new boolean[100001];
        timezone = new int[100001];
        BFS();
        System.out.println(timezone[brother] - 1);
    }

    private static void BFS() {
        LinkedList<int[]> que = new LinkedList<>();
        que.add(new int[]{me, 1});
        visit[me] = true;
        timezone[me] = 1;

        while (!que.isEmpty()) {
            int[] poll = que.poll();
            int idx = poll[0];
            int time = poll[1];

            if (idx + 1 >= 0 && idx + 1 <= 100000) {
                if (!visit[idx + 1] || timezone[idx + 1] > time + 1) {
                    visit[idx + 1] = true;
                    timezone[idx + 1] = time + 1;
                    que.add(new int[]{idx + 1, time + 1});
                }
            }

            if (idx - 1 >= 0 && idx - 1 <= 100000) {
                if (!visit[idx - 1] || timezone[idx - 1] > time + 1) {
                    visit[idx - 1] = true;
                    timezone[idx - 1] = time + 1;
                    que.add(new int[]{idx - 1, time + 1});
                }
            }

            if (idx * 2 >= 0 && idx * 2 <= 100000) {
                if (!visit[idx * 2] || timezone[idx * 2] > time) {
                    visit[idx * 2] = true;
                    timezone[idx * 2] = time;
                    que.add(new int[]{idx * 2, time});
                }
            }
        }
    }
}