[BOJ] 13549 - 숨바꼭질 3

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

난이도: 골드 5

사용언어: JAVA

 

풀이

비록 이차원이 아닌 일차원 배열에 입력이 들어가지만, 이 문제는 BFS를 사용하여 접근하는 것이 가장 이해하기 쉽습니다. 기존에 이차원 배열에서 상하좌우로 이동하던 것을, 좌우로 한 칸씩, 또는 2배씩 이동시키는 것으로 변형한다고 생각하면 됩니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/63

[BOJ] 2178 - 미로 탐색

 

그리고 한 가지 고려해야 할 사항은 목표 지점인 K에 도달했다고 해서 섣불리 결과를 출력해서는 안됩니다. 혹시 그 뒤에 (2*X 연산을 더 많이 해서) 시간 값이 더 작은 수빈이가 도착할 수도 있기 때문입니다. 따라서 적어도 큐에 저장되어 있는 수빈이들은 다 확인을 한 뒤에 최소 시간을 판단해야 합니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static class position{
        int pos;
        int second;
    }
 
    static Queue<position> q= new LinkedList<>();
    static int []d = {1,-1};
    static int N, K;
    static int result;
    static int count = 2;
    static int flag = 0;
    public static void bfs(position p, int arr[]){
        int i;
        for(i=0;i<2;i++){
            if(p.pos+d[i] >= 0 && p.pos+d[i] <=100000 && (arr[p.pos+d[i]] == 0||arr[p.pos+d[i]] == count)){ // 위치가 범위내에 있고, 아직 아무도 검사하지 않았거나, 해당 사이클 안에서만 검사되었을 경우
                if(p.pos+d[i] == K){ // 동생을 찾았다면
                    result = Math.min(p.second+1,result); // 결과 저장
                    flag = 1;
                }
                else{
                    arr[p.pos+d[i]] = count; // 카운트 값을 넣어줌으로써 이미 방문했던 곳임을 마킹
                }
                position p1 = new position();
                p1.pos = p.pos+d[i];
                p1.second = p.second + 1; // 한 칸 이동하는 데에는 1초가 소요
                q.add(p1); // 위치와 현재까지의 소요시간을 큐에 삽입
            }
            if(p.pos*2*d[i] >= 0 && p.pos*2*d[i] <=100000 &&  (arr[p.pos*2*d[i]] == 0||arr[p.pos*2*d[i]] == count)){ // 위치가 범위내에 있고, 아직 아무도 검사하지 않았거나, 해당 사이클 안에서만 검사되었을 경우
                if(p.pos*2*d[i] == K){ // 동생을 찾았다면
                    result = Math.min(p.second,result); // 결과 저장
                    flag = 1;
                }
                else{
                    arr[p.pos*2*d[i]] =count; // 카운트 값을 넣어줌으로써 이미 방문했던 곳임을 마킹
                }
                position p2 = new position();
                p2.pos = p.pos*2*d[i];
                p2.second = p.second; // 순간이동에는 0초가 소요
                q.add(p2); // 위치와 현재까지의 소요시간을 큐에 삽입
            }
        }
    }
 
    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());
        int[]arr = new int[100001]; // 수빈이가 움직일 수 있는 곳 배열
        int i, k;
        position p = new position();
 
        if(N == K){ // 수빈이와 동생이 같은 곳에 위치하는 경우 예외 처리
            System.out.println(0);
            System.exit(0);
        }
        p.pos = N;
        p.second = 0;
        q.add(p); // 수빈이의 현재 위치와 현재까지 소요시간인 0을 큐에 삽입
        arr[p.pos] = 1; // count 값을 1은 여기서 넣어주기 때문에 2부터 시작
 
        result = Integer.MAX_VALUE;
        while(true){ // 이 while 문 한 번을 한 사이클이라고 하자.
            k = q.size();
            for(i=0;i<k;i++){
                p = q.remove(); // 큐에서 하나씩 빼서
               bfs(p, arr); // bfs 수행
            }
            if(flag == 1){ // K에 도달했다면
                System.out.println(result); // 결과 출력
                System.exit(0);
            }
            count++; //count는 이미 왔던 곳을 다시 검사하지 않기 위해, 그리고 한 사이클 안에서는 한 수빈이가 특정 지점에 먼저 도착하더라도 다른 수빈이가 검사를 할 수 있도록 해주는데 사용
        }
    }
}