[Java / 백준 ] 12851. 숨바꼭질

문제

링크: https://www.acmicpc.net/problem/12851

태그: bfs

 

풀이

 숨바꼭질 문제와 동일하지만, 다른 점이 있다면 이미 방문한 지점도 재방문이 가능하도록 해야한다는 것입니다.

재방문이 가능한 기준은 이전에 방문했던 시간과 다시 방문하려고 할때의 도달 시간이 같을 때입니다.

다시 방문하려고 할때, 이전에 도달했던 시간보다 크다면, K에 도달했을 때 최단 시간이 될 가능성이 없기 때문에 제외시켜줍니다.

 

vis 배열을 선언해주고 이를 모두 최대값으로 초기화 해준 다음, vis[next] <= cnt 라면 큐에 다시 넣어주었습니다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N, K;
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());

    int[] vis = new int[100002];
    for(int i=0; i<100002; ++i) {
      vis[i] = Integer.MAX_VALUE;
    }
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{N, 0});
    vis[N] = 0;
    int ans = 100001; // 찾는데까지 걸리는 횟수
    int ansCnt = 0; // 그 개수
    while(!q.isEmpty()) {
      int[] cur = q.poll();

      if(cur[0] == K && ans == 100001) {
        ans = cur[1];
        ansCnt++;
      } else if(cur[0] == K && ans == cur[1]) {
        ansCnt++;
      }

      int n1 = cur[0] + 1;
      int n2 = cur[0] - 1;
      int n3 = cur[0] * 2;
      int nCnt = cur[1] + 1;

      if(n1 >= 0 && n1 <= 100001 && nCnt < ans && vis[n1] >= nCnt) {
        vis[n1] = nCnt;
        q.add(new int[]{n1, nCnt});
      }

      if(n2 >= 0 && n2 <= 100001 && nCnt < ans && vis[n2] >= nCnt) {
        vis[n2] = nCnt;
        q.add(new int[]{n2, nCnt});
      }

      if(n3 >= 0 && n3 <= 100001 && nCnt < ans && vis[n3] >= nCnt) {
        vis[n3] = nCnt;
        q.add(new int[]{n3, nCnt});
      }

    }


    System.out.println(ans);
    System.out.println(ansCnt);

  }
}