[java 백준]실버 1/1697번 숨바꼭질

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

1697번: 숨바꼭질

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int n, m;
    public static int cnt = 0;
    public static boolean[] visited = new boolean[100001];
 
    public static void BFS(int n) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(n);
 
        visited[n] = true;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
 
            for (int i = 0; i < queueSize; i++) {
                ArrayList<Integer> arr = new ArrayList<Integer>();
                int num = queue.poll();
 
                if (num == m) {
 
                    return;
                }
 
                arr.add(num * 2);
                arr.add(num + 1);
                arr.add(num - 1);
 
                for (int j = 0; j < arr.size(); j++) {
 
                    if (arr.get(j) >= 0 && arr.get(j) <= 100000) {
 
                        if (!visited[arr.get(j)]) {
                            visited[arr.get(j)] = true;
                            queue.add(arr.get(j));
                        }
 
                    }
                }
 
            }
            cnt++;
 
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        if (n == m) {
            System.out.println(0);
 
        } else {
            BFS(n);
            System.out.println(cnt);
        }
 
    }
 
}

 

정말 오랜만에 온전히 내 힘으로 푼 문제인데 아마 밑에 너비우선탐색이라 적혀있지 않았으면 못풀었을수도 있다 ㅋㅋ

문제를 풀면서 while문으로만 컨트롤하려니까 문제가 많았는데 그냥 BFS메서드 하나 만들어줘서 거기에 BFS구현하고 num==m이면 함수 return해줄수 있게 해주니까 금방 풀렸다.

 

이런식으로 가지치기가 가능하다. 그래서 큐에 세로 한줄 씩 담아서 인접노드 탐색해주면 된다! 

빨간펜 친것 처럼 세로 한줄씩 담아주면 된다