b1697_숨바꼭질

b1697_숨바꼭질

package com.hotfive.workbook.b1697_숨바꼭질; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int V; static int second; static int [] visited; public static void main(String[] args) { Scanner sc = new Scanner(System.in); V = sc.nextInt(); //0 ≤ N ≤ 100,000 int K = sc.nextInt(); //0 ≤ K ≤ 100,000 second = 0; visited = new int[100001]; // index가 위치, 값은 second if(V!=K) bfs(V,K); System.out.println(second); sc.close(); } private static void bfs(int v, int k) { Queue queue = new LinkedList<>(); queue.add(v); visited[v]++; //System.out.println(v + " "+visited[v]); while (!queue.isEmpty()){ v = queue.poll(); int next = 0; for (int i = 0; i < 3; i++) { switch (i){ case 0 : next = v + 1; break; case 1 : next = v - 1; break; case 2 : next = v * 2; break; } if(next>=0 && next <=100000 && visited[next]==0) { visited[next] = visited[v] + 1; // 이동전의 시간 + 1 if(next == k){ second = visited[next]-1; return; } queue.add(next); } //System.out.println(next + " "+visited[next]); } } } }

이동하는 위치를 index로 가지는 배열을 만들어서 BFS를 실행하였다.

이동하는 방법은 3가지이기 때문에 세가지 전부 해봐야한다. 그래서 for문으로 세번 반복하게끔 처리하였다.

배열에 해당 위치마다 몇초가 지났는지 알 수 있게끔 값을 저장하고, 한번 이동할 때마다 1씩 증가하게끔 이동 전의 시간 + 1 을 해주었다.

주의: 배열을 사용하기 때문에 다음 이동하는 위치가 ArrayIndex 벗어나지 않게 next>=0 && next <=100000 로 처리해줘야한다.

from http://elevensix.tistory.com/81 by ccl(A) rewrite - 2021-09-18 02:28:03