1697번

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

1697번: 숨바꼭질

이번 문제는 가장 적은 시간. 즉, 최소시간을 구하는 문제였다.

최소 시간을 구하기 위해서는 BFS가 제일 적합하다고 생각했다. 문제의 분류 또한 그렇게 나와 있었다.

DFS로 하기에는 최소를 구할 수 있다는 보장이 부족하고, 하나, 하나의 탐색 시간이 아주 오래걸릴 확률이 있기 때문에, BFS로 풀었다.

원리는 BFS의 큰 틀에 조금의 조건을 부합시켰다.

조건은 일단 큐에 들어갈 값이 방문여부를 확인하는 범위를 벗어나지 않는지 확인하는 것이다.

매초 -1로, 매초 +1로, 매초 *2로 가는 방법이 있는데 그것들을 모두 큐에 넣는 방식으로 맨처음에는 단순히 시도해 보았다. 하지만

메모리 초과가 발생했다. 그 이유는 처음에 바보처럼(?) "방문한 곳을 또 방문할 수 있지 않을까?"라고 이상한 생각을 해서  방문처리를 하지 않아서 방문했던 부분을 다시 방문한 경우 때문이었다.

그 다음에는 방문처리를 하는 과정에서 index범위 오류가 발생했고 이를 조건문으로 해결하였다.

그리고 시간 카운팅은 내부에서 시간을 계산하는 방식으로 저번에 풀은 2178번 문제와 마찬가지로 해결했다.

 

내부 카운팅이 무슨 소리인지는 아래의 글을 보면서 이해 할 수 있을 것 같다.

https://parkjunbackend.tistory.com/56

b2178번

이 문제에서 주의 할 것은 0 또한 좌표에 포함된다는 것이다.

그 외에는 방문리스트의 범위 정도이다.

 

나는 방문처리 리스트를 int형으로 하여서 1이면 방문 0이면 비방문으로 처리했다.

매초*2와 매초+1은 100000보다 작거나 같아야하는 조건이 있고, 매초-1은 0보다 크거나 같아야한다는 조건이 있다.

나머지는 BFS의 원리 그대로 탐색을 진행하는 것이다.

 

package backjoon.b1697;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class b1697 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        Graph g = new Graph(N,K);
        g.bfs(N);
        System.out.println(g.count);
    }
}
class Graph{
    int[] arr;
    int N;
    int K;
    int count = 0;
    Queue<target> queue = new LinkedList<>();
    public Graph(int N,int K){
        this.N=N;
        this.K=K;
        arr = new int[100001];
    }
    public void bfs(int R){
        queue.add(new target(R,0));
        arr[R]=1;
        while (!queue.isEmpty()){
            target tmp = queue.poll();
            if(tmp.x==K){
                count=tmp.cnt;
                return;
            }
            for(int i=0; i<3; i++) {
                if(tmp.x-1>=0) {
                    if (arr[tmp.x - 1] != 1) {
                        queue.add(new target(tmp.x - 1, tmp.cnt + 1));
                        arr[tmp.x - 1] = 1;
                    }
                }
                if(tmp.x+1<=100000) {
                    if (arr[tmp.x + 1] != 1) {
                        queue.add(new target(tmp.x + 1, tmp.cnt + 1));
                        arr[tmp.x + 1] = 1;
                    }
                }
                if(tmp.x*2<=100000){
                    if (arr[tmp.x * 2] != 1) {
                        queue.add(new target(tmp.x * 2, tmp.cnt + 1));
                        arr[tmp.x*2]=1;
                    }
                }
            }
        }
    }
}
//1 23->2 3 6 12 24 23
class target{
    int cnt;
    int x;
    public target(int x, int cnt){
        this.x=x;
        this.cnt=cnt;
    }
}