[백준] 13549번 : 숨바꼭질 3 - 자바[Java]

13549번: 숨바꼭질 3

풀이

BFS를 사용하여 시작 위치에서 도착 위치까지 가는 최소 시간을 구한다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        System.out.println(bfs(start, end));
    }

    static int bfs(int start, int end) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);

        int[] dis = new int[100001];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[start] = 0;

        while (!q.isEmpty()) {
            int pos = q.poll();

            if (pos == end)
                return dis[end];

            if (checkIndex(pos + 1) && (dis[pos+1] > dis[pos] + 1)) {
                dis[pos+1] = dis[pos] + 1;
                q.add(pos+1);
            }
            if (checkIndex(pos - 1) && dis[pos-1] > dis[pos] + 1) {
                dis[pos-1] = dis[pos] + 1;
                q.add(pos-1);
            }
            if (checkIndex(pos * 2) && dis[pos*2] > dis[pos]) {
                dis[pos * 2] = dis[pos];
                q.add(pos*2);
            }
        }

        return -1;
    }

    static boolean checkIndex(int n) {
        if (n >= 0 && n <= 100000)
            return true;
        return false;
    }

}

 

다른 풀이 - 2

Queue에 (위치, 시간)을 저장하고, visited를 사용해 방문 여부를 체크한다.

이 때 Queue에 넣는 순서를 *2 -> -1 -> 1 순서로 해야 한다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        System.out.println(bfs(start, end));
    }

    static int bfs(int start, int end) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start, 0});

        boolean[] visited = new boolean[100001];
        visited[start] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int pos = cur[0];
            int sec = cur[1];
            if(pos == end) {
                return sec;
            }

            if (checkIndex(pos * 2) && !visited[pos*2]) {
                visited[pos*2] = true;
                q.add(new int[]{pos*2, sec});
            }
            if (checkIndex(pos - 1) && !visited[pos-1]) {
                visited[pos-1] = true;
                q.add(new int[]{pos-1, sec + 1});
            }
            if (checkIndex(pos + 1) && !visited[pos+1]) {
                visited[pos+1] = true;
                q.add(new int[]{pos+1, sec + 1});
            }
        }

        return -1;
    }

    static boolean checkIndex(int n) {
        if (n >= 0 && n <= 100000)
            return true;
        return false;
    }

}