[골드5] 13549. 숨바꼭질 3 (Java)

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

13549번: 숨바꼭질 3

 Thanks to Judy Lee ~22

---

※  문제를 요약하면 아래와 같습니다.

▶ 수빈이는 동생이랑 숨바꼭질 중이며, 수빈이 는 점 N, 동생은 점 K에 위치

▶ 수빈이는 걷거나 순간이동이 가능 걷는다면 1초후에 현재 위치 +1, 현재 위치-1로 이동

▶ 순간이동을 하는 경우 현재 위치 *2의 값으로 이동

▶ 수빈이가 동생을 찾을 수 있는 가장 빠른 시간 출력

▶ Input : 첫번째 줄에 공백을 기준으로 수빈 위치 N, 동생 위치 K가 입력

▶ Output : 수빈이가 동생을 찾는 가장 빠른 시간 출력

---

◈ Input - 1

5 17

◈ Output - 1

2

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 최소 시간 == 현재시간 *2, -1, +1 순서대로 BFS 

▶ 이미 탐색한 곳은 방문 처리, N과 K 중 큰 수의 2배 크기로 boolean 배열 선언

▶ 현재 포인트와 시간을 저장하고 있는 Point 클래스 구현

▶ Point 중심으로 BFS 진행, K에 최초 도달 시 BFS 종료, Count 출력 

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
	int m_nNum;
	int m_nCount;

	public Point(int m_nNum, int m_nCount) {
		super();
		this.m_nNum = m_nNum;
		this.m_nCount = m_nCount;
	}
}

public class Main {
	static int N, K, nMax;
	static boolean[] barrVisit;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		if(N > K)
			nMax = N;
		else
			nMax = K;
		
		barrVisit = new boolean[(nMax+1) * 2];
		int nResult = BFS();
		
		bWriter.write(String.valueOf(nResult));
		bWriter.close();
	}

	private static int BFS() {
		// TODO Auto-generated method stub
		Queue<Point> qBFS = new LinkedList<>();
		qBFS.add(new Point(N, 0));
		barrVisit[N] = true;
		
		while(!qBFS.isEmpty()) {
			Point p = qBFS.poll();
			
			int nPlus = p.m_nNum +1;
			int nMinus = p.m_nNum -1;
			int nMul = p.m_nNum * 2;
			
			if(p.m_nNum == K) {
				return p.m_nCount;
			}
			
			if(nMul < (nMax+1) * 2 && !barrVisit[nMul] ) {
				barrVisit[nMul] = true;
				qBFS.add(new Point(nMul, p.m_nCount));
			}
			if(nMinus >= 0 && !barrVisit[nMinus]) {
				barrVisit[nMinus] = true;
				qBFS.add(new Point(nMinus, p.m_nCount+1));
			}
			if(nPlus < (nMax+1) * 2 && !barrVisit[nPlus]) {
				barrVisit[nPlus] = true;
				qBFS.add(new Point(nPlus, p.m_nCount+1));
			}
		}
		return 0;
	}
}

---

Good Luck! (피드백 감사합니다!)