백준 알고리즘_13549_숨바꼭질3
https://www.acmicpc.net/problem/13549
문제 설명
이번엔 2X만큼 이동하는 것이 1초가 아닌 0초가 걸린다는 문제이다.
문제 풀이
처음엔 그냥
2*X
해줄때의step
만 카운트 하지않고q
에 넣어줬다.
주어진 예제인5, 17
로 돌려보니 정답인2
가 나오길래 별 생각없이 제출했다. 그랬더니 틀렸다.
왜 틀렸는지 알기 위해서는 또 다른 예제가 필요했다.
이번엔5 15
를 입력했는데 결과가3
이 나왔다. 원래는2
가 나와야 한다.
5 > 4 > 8 > 16 > 15
이렇게가2 Step
이다.
왜2
가 안나오고3
이 나오는지 알기 위해서 디버깅을 했다.
그랬더니...step
이3
인 값이2
인 것보다q
에서 더 빨리 나오기 때문이었다.
즉,'nowN == K' 지만 step은 최소가 "아닌" 것이 "먼저" 도달할 수 있다
는 것이다.
if(n == K) {
System.out.println(stepInfo.step);
}
따라서 기존의 이 부분을 수정해 줄 필요가 있었다.
if(n == K) {
//System.out.println("n == K 일때 >> "+stepInfo.step);
answerList.add(new answerCandidate(stepInfo.step));
}
고심한 결과,
answerCandidate
라는 클래스를 하나 더 만들 필요가 있었다.n == k
일 때마다List<answerCandidate> answerList
객체에step
을 저장했다.
//걸음수 오름차순 정렬하여 최소걸음수 찾기
Collections.sort(answerList, new Comparator<answerCandidate>(){
@Override
public int compare(answerCandidate o1, answerCandidate o2) {
return Double.compare(o1.step, o2.step); //오름차순
}
});
System.out.println(answerList.get(0).step);
그리고
main
에서 오름차순으로 정렬해, 맨 앞에껄 출력했다.
그렇게 해주었는데도 여전히3
을 리턴하고 있었다..
도저히 이해가 안돼서 다시 디버깅을 돌렸다.
16 > 15
로 가는 과정에서15
가 이미visited == true
상태였기 때문에 그냥 건너뛰어져버린 것이었다.
결국, 방문체크를말고, 꺼낸 직후에 하는게 맞았다.q
에 넣은 직후
전체 코드
public class Practice2 {
static int N;
static int K;
static boolean[] check = new boolean[100001];
static int numberOfSearching = 0;
static List<answerCandidate> answerList = new ArrayList<>();
public static class StepInfo{
int nowN;
int step;
public StepInfo(int nowN, int step) {
this.nowN = nowN;
this.step = step;
}
}
public static class answerCandidate{
int step;
public answerCandidate(int step) {
this.step = step;
}
}
public static void main(String[] args) {
input();
StepInfo stepInfo = new StepInfo(N, 0);
Queue<StepInfo> q = new LinkedList<>();
q.add(stepInfo);
hideAndSeek(q);
//걸음수 오름차순 정렬하여 최소걸음수 찾기
Collections.sort(answerList, new Comparator<answerCandidate>(){
@Override
public int compare(answerCandidate o1, answerCandidate o2) {
return Double.compare(o1.step, o2.step); //오름차순
}
});
System.out.println(answerList.get(0).step);
}
private static void hideAndSeek(Queue<StepInfo> q) {
while(!q.isEmpty()) {
StepInfo stepInfo = q.poll();
int n = stepInfo.nowN;
check[n] = true;
// 'nowN = K' 지만 step은 최소가 "아닌" 것이 "먼저" 도달할 수 있다.
// 최소인 step을 언제 알수있지? '언제까지' 돌려야 하지? 무한정 돌릴순 없는거자나...
if(n == K) {
//System.out.println("n == K 일때 >> "+stepInfo.step);
answerList.add(new answerCandidate(stepInfo.step));
}
// +1, -1, *2 셋 중 어느 연산을 할 건지 탐색
StepInfo nextStep;
int tempN;
for(int d = 0; d < 3; d++) {
switch(d) {
case 0:
tempN = n;
tempN += 1;
if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
nextStep = new StepInfo(tempN, stepInfo.step + 1);
q.add(nextStep);
//check[tempN] = true;
}
break;
case 1:
tempN = n;
tempN -= 1;
if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
nextStep = new StepInfo(tempN, stepInfo.step + 1);
q.add(nextStep);
//check[tempN] = true;
}
break;
case 2:
tempN = n;
tempN *= 2;
if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
nextStep = new StepInfo(tempN, stepInfo.step);
q.add(nextStep);
//check[tempN] = true;
}
break;
}
}
}
}
private static void input() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
}
}
Git gist 주소
https://gist.github.com/ysyS2ysy/0dfdaf29889f6030e2e952d120844b28
Author And Source
이 문제에 관하여(백준 알고리즘_13549_숨바꼭질3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dtd1170/백준-알고리즘13549숨바꼭질3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)