22.11.09 - [BOJ] 13549. 숨바꼭질 3

[suhyunsim]

문제

• 13549

핵심 아이디어

• 큐를 사용한 BFS 문제
• 기존 풀이보다 더 쉬운 풀이로 수정

어려운 점, 실수

• 21.07.07 - [BOJ] 1697. 숨바꼭질 #119 문제의 풀이에서 순간이동 하는 경우 1초 후에 이동하는 것 -> 0초 후에 이동하는 것 이 차이밖에 없는데 기존 풀이에서 해당 부분만 변경해서는 풀리지 않는다.
• 왜? 순간이동을 하는 경우를 가장 먼저 계산해줘야 하기 때문이다. 순간이동의 경우 시간이 들지 않기 때문에 방문처리를 할 경우 가장 먼저 되어야 한다.
• 가중치가 다르기 때문에 x * 2(순간이동) -> x - 1(뒤로) -> x + 1(앞으로) 순서로 계산해야 한다.

풀이

기존 풀이 시간 변경 & 순간이동 -> 뒤로 -> 앞으로

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int MAX = 200000;
        Queue<Integer> queue = new LinkedList<>();
        int[] dist = new int[MAX];
        boolean[] check = new boolean[MAX];
        check[n] = true;
        dist[n] = 0;
        
        queue.offer(n);
        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now * 2 < MAX) {
                if (!check[now * 2]) {
                    queue.offer(now * 2);
                    check[now * 2] = true;
                    dist[now * 2] = dist[now];                    
                }
            }
            if (now - 1 >= 0) {
                if(!check[now - 1]) {
                    queue.offer(now - 1);
                    check[now - 1] = true;
                    dist[now - 1] = dist[now] + 1;
                }
            }
            if (now + 1 < MAX) {                
                if (!check[now + 1]) {
                    queue.offer(now + 1);
                    check[now + 1] = true;
                    dist[now + 1] = dist[now] + 1;
                }
            }

        }
        bw.write(String.valueOf(dist[k]));
        bw.flush();
        bw.close();
        br.close();
    }    
}

다른 풀이

package main.java.com.poogle.BOJ;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int max = 100000;
    static int min = Integer.MAX_VALUE;
    static int n, k;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        visited = new boolean[max + 1];
        bfs();
        System.out.println(min);
    }

    public static void bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(n, 0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            visited[node.x] = true;
            if (node.x == k) {
                min = Math.min(min, node.time);
            }
            if (node.x * 2 <= max && !visited[node.x * 2]) {
                queue.offer(new Node(node.x * 2, node.time));
            }
            if (node.x + 1 <= max && !visited[node.x + 1]) {
                queue.offer(new Node(node.x + 1, node.time + 1));
            }
            if (node.x - 1 >= 0 && !visited[node.x - 1]) {
                queue.offer(new Node(node.x - 1, node.time + 1));
            }
        }
    }
}

class Node {
    int x, time;

    public Node(int x, int time) {
        this.x = x;
        this.time = time;
    }
}