글 읽기 - 35%틀렸는데 이유를 모르겠습니다.

hwj0623 7년 전 0

1 2

2 4

1 10 과 같은 중복 방문 고려해야 하는 테스트 케이스 다 해결했는데 잘 되다가 왜 틀렸다고 하는 걸까요?

예외케이스를 알았으면 합니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int n, k;
	static int d[];
	static int ret;
	static boolean visit[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		d = new int [200_010];
		visit = new boolean [200_010];
		ret = 0;
		for(int i=0; i<d.length; i++){
			d[i] = Integer.MAX_VALUE-1;
		}
		d[n]=0;
		bfs(n, k);
		System.out.println(d[k]);
		System.out.println(ret);
	}
	public static void bfs(int s, int e){
		Queue<Integer>queue = new LinkedList<Integer>();
		queue.add(s);
		visit[s] = true; //스타트에 대해 true처리
		if(s==e){
			d[e]=0;
			return;
		}
		while(!queue.isEmpty()){
			int cur = queue.poll();
//			System.out.println("cur : "+cur);

			//add adjacent node
			if(cur-1>0){
				if(d[cur-1]>=d[cur]+1){
					queue.offer(cur-1);
					d[cur-1] = d[cur]+1;
					if (cur-1==e){
						ret++;
					}
				}	
			}
			if(cur+1 <=100000){
				if(d[cur+1]>=d[cur]+1){
					queue.offer(cur+1);
					d[cur+1] = d[cur]+1;
					if(cur+1 ==e){
						ret++;
					}
				}	
			}
			if(cur*2 <=100000){
				if(d[cur*2]>=d[cur]+1){
					queue.offer(cur*2);
					d[cur*2] = d[cur]+1;
					if (cur*2==e){
						ret++;
					}
				}
			}
			if(cur==e){
				break;
			}
		}
	}
}

zlzmsrhak 7년 전 0

n = k일 때와 k가 0일 때 답이 제대로 안나옵니다.

hwj0623 7년 전 0

감사합니다. 수정해보겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

35%틀렸는데 이유를 모르겠습니다.

hwj0623 7년 전 0

zlzmsrhak 7년 전 0

hwj0623 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말