👌 숨바꼭질3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
✔ 접근방법
기본적인 BFS를 사용하여 해결.
- 시작위치 포지션을 큐에 삽입
- 큐의 pos와 time을 임시저장 후 dequeue
- pos와 종료위치가 같을경우 리턴
- pos*2, pos-1, 그리고 pos+1 각 상황이 방문되지 않았을 경우, 새로운 포지션을 생성해서 큐에 삽입 및 방문으로 마크
- 2-4 반복
*처음에는 따로 visit을 설정하지 않고 해결하려 했으나, 겹치는 경우가 많이 발생하여 큰 숫자에서는 오버플로우가 발생 -> visited 리스트를 생성하여 프루닝을 가능토록 했다.
✔ 코드
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
public class p13549 {
//pos와 time을 변수로 가지는 Position 클래스 확립
static class Position{
int pos;
int time;
public Position(int pos, int time) {
this.pos = pos;
this.time = time;
}
}
public static void main(String[] args) {
//이미 방문한 포지션들을 프루닝해주기 위한 리스트 선언
boolean[] visited = new boolean[100001];
//사용자 인풋 및 에러확인
Scanner scan = new Scanner(System.in);
int a = scan.nextInt();
int b = scan.nextInt();
if (a < 0 || a > 100000 || b < 0 || a > 100000) {
System.out.println("Invalid Input");
return;
}
//큐 선언 및 시작점 큐에 삽입
Queue<Position> q = new LinkedList<>();
q.add(new Position(a, 0));
//반복문
while(!q.isEmpty()){
//큐의 pos와 time을 임시저장 후 dequeue
int tempPos = q.peek().pos;
int tempTime = q.peek().time;
q.poll();
//해당 포지션이 아직 방문되지 않았을 경우,
//각 상황에 따라 알맞은 pos와 time으로 새로운 Position을 생성해서 큐에 삽입 후
//해당 포지션을 방문으로 마크
if(tempPos == b){
System.out.println(tempTime);
return;
}
if(tempPos * 2 <= 100000 && !visited[tempPos*2]){
q.add(new Position(tempPos*2, tempTime));
visited[tempPos*2] = true;
}
if(tempPos - 1 >= 0 && !visited[tempPos-1]){
q.add(new Position(tempPos-1, tempTime+1));
visited[tempPos - 1] = true;
}
if(tempPos + 1 <= 100000 && !visited[tempPos+1]){
q.add(new Position(tempPos+1, tempTime+1));
visited[tempPos + 1] = true;
}
}
}
}
☝ 팁
방문기록을 노드에 initialize하기 힘든 경우에는, 간단하게
boolean list로 reference 가능boolean[] visited = new boolean[100001];
