글 읽기 - [java] 이클립스에서는 되는데 바로 틀렸다고 뜹니다..

dl0312 6년 전 0

BFS 사용해서 풀었는데 바로 틀렸다고 뜨네요... 뭘 잘못푼걸까요

//	BOJ - 1697
//	Algorithm - BFS


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

public class Main {
	
	static int a;	//	subin's position
	static int b;	//	sister's position
	static boolean [] visit = new boolean [200002];
	static class Pos{
		int x;
		int cnt;
		
		public Pos(int x, int cnt) {
			this.x = x;
			this.cnt = cnt;
		}
	}
	static Queue <Pos> q = new <Pos> LinkedList(); // 시행을 큐에 저장해라!!!

	public static int BFS(Pos now) {
		Pos tmp = now;
		q.offer(now);
		visit[now.x] = true;
		while(true) {
			now = q.poll();
			if(now.x == b) {
				return now.cnt;
			}
			//System.out.print(now.x + " ");
			if(now.x-1>=0 && b < now.x*2 && !visit[now.x-1]) {
				tmp = new Pos(now.x-1,now.cnt+1);
				q.offer(tmp);
				visit[now.x-1] = true;
				/*
				if(tmp.x == b) {
					return tmp.cnt;
				}
				*/
			}
			if(b>now.x && !visit[now.x+1]) {
				tmp = new Pos(now.x+1,now.cnt+1);
				q.offer(tmp);
				visit[now.x+1] = true;
				/*
				if(tmp.x == b) {
					return tmp.cnt;
				}
				*/
			}
			if( b > now.x && !visit[now.x*2]) {
				tmp = new Pos(now.x*2,now.cnt+1);
				q.offer(tmp);
				visit[now.x*2] = true;
				/*
				if(tmp.x == b) {
					return tmp.cnt;
				}
				*/
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn = new Scanner(System.in);
		a= scn.nextInt();
		b= scn.nextInt();
		for( int i=0;i<200002;i++) {
			visit[i] = false;
		}
		if(a!=b) System.out.print(BFS(new Pos(a,0)));
		else System.out.print(0);
	}
}

djm03178 6년 전 1

5 16

-> 4 -> 8 -> 16으로 3초만에 갈 수 있습니다.

dl0312 6년 전 0

감사합니다! -1 조건에서 if(now.x-1>=0 && !visit[now.x-1])로 수정하니 돌아갑니다

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

문제

문제

출처

ICPC

[java] 이클립스에서는 되는데 바로 틀렸다고 뜹니다..

dl0312 6년 전 0

djm03178 6년 전 1

dl0312 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말