[백준 3주차 - 17071] 숨바꼭질 5 (Java)

📌 문제

 

 

📝 풀이과정

위 문제를 푸는 데 2가지 핵심로직이 있다

 

1) 수빈이와 동생이 같이 이동하면서 만났을 경우

 

2) 수빈이가 먼저 도착했지만, 동생과 홀수, 짝수가 맞았을 경우

ex) 수빈이는 2초에 20에 도착, 동생은 4초에 20에 도착해도 성립된다

수빈이는 +1, -1으로 이동할 수 있기 때문에 20(2초) → 21(3초) → 20(4초) 로 동생과 만날 수 있다

 

 

⚠️ 처음에 1)번째 상황만 생각해서 문제를 풀었기 때문에 틀렸다.....

 

💻 코드

import java.util.Scanner;
import java.io.*;
import java.util.*;

public class Main{
	static final int MAX=500000;
	static int[][] visited=new int[2][MAX+4]; //홀,짝을 맞추기 위해
	static boolean check=false;
	static int n,k;
	static int turn;

	static void bfs(int here){
		visited[0][here]=1;
		Queue<Integer> queue=new LinkedList<>();
		queue.add(here);

		turn=1;
		while(!queue.isEmpty()){
			k+=turn;
			if(k>MAX) break;
			
			if(visited[turn%2][k]>0){ //turn초(홀수or짝수)일때 동생위치k에 수빈이가 방문했다면
				check=true;
				break;
			}
			int qSize=queue.size(); //플러드필, 단계별로 분리하고 싶을때 
			for(int i=0;i<qSize;i++){
				int now=queue.poll();
				for(int next:new int[]{now-1, now+1, 2*now}){
					if(next<0 || next>MAX || visited[turn%2][next]>0) continue;
					visited[turn%2][next]=visited[(turn+1)%2][now]+1; //짝수에 방문했다면 그 전은 홀수
					if(next==k){ //동생위치와 수빈이위치가 같을 때
						check=true;
						break;
					}
					queue.add(next);
				}
				if(check) break;
			}
			if(check) break;
			turn++;
		}
		
	}
    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());
		
		if(n==k){
			System.out.println(0);
			return;
		}
		bfs(n);
		
		if(check){
			System.out.println(turn);
		}
		else{
			System.out.println(-1);
		}
	}
}