백준 1697 자바 - 숨바꼭질 문제

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

이문제는 bfs를 통해서 수빈이를 3가지 경우 모두 움직여보면서 방문처리를 하고 수빈이가 동생의 위치에 방문했을 경우의 시간을 출력하면되는 문제이다.

 

주의해야할 부분이라면 위치와 시간을 포함하는 자료구조(객체)를 만들지 않는 경우 시간을 잘 관리햐아한다는 것인데

큐가 빌때 까지 돌아야하지만 시간은 큐에 사이즈만큼 돌때마다 늘려야한다.

시간이 0초일때는 시작 지점 1개만 큐에 들어온다

시간이 1초일때는 시작지점에서 3가지 방향으로 간 경우가 큐에 들어온다.

시간이 2초일때는 앞선 시간에 3가지 방향에 각각 3가지 방향을 더해서 9가지가 큐에 들어온다.

현재 큐의 사이즈 = 이전 큐의 사이즈 * 3 - 중복인 경우 라고 볼수 있다.

그래서 큐에서 꺼내서 로직을 돌리기전에 몇번꺼내서 로직을 돌려야하는지 알아야하는 것이다.

for(int j = 0, size = q.size(); j < size; j++) {
	...
}
time++;

 

 

 

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

// 숨바꼭질 문제 - 1697번
public class HideAndSeek1 {

    static int N, K;
    static int time;
    static boolean[] visited = new boolean[100001];

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if(N == K){
            System.out.println(0);
        }else {
            bfs(N);
            System.out.println(time);
        }
    }

    static void bfs(int start) {
        time = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            // 만난 경우
            if(visited[K]) {
                return;
            }

            // 현재 q의 사이즈 만큼만 돌리기 - 시간 계산을 위해서
            for(int j = 0, size = q.size(); j < size; j++) {
                int now = q.poll();
                int next;

                // 다음에서 영역을 방문 처리
                next = now - 1;
                if(next >= 0 && !visited[next]) {
                    visited[next] = true;
                    q.offer(next);
                }

                next = now + 1;
                if(next < 100001 && !visited[next]) {
                    visited[next] = true;
                    q.offer(next);
                }

                next = now * 2;
                if(next < 100001 && !visited[next]) {
                    visited[next] = true;
                    q.offer(next);
                }
            }
            time++;
        }
    }
}