글 읽기 - [JAVA] 20% 이후에 실패가 됩니다.

ston13 6년 전 0

책이나 다른 분들의 로직을 그대로 구현했다고 생각했는데 20% 이후에 계속 실패가 됩니다.

잘못된 부분이 있는지 확인해 주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	public static boolean adj[][];
	public static boolean visited[];
	public static int N;
	public static String Answer;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader reader = new BufferedReader( new InputStreamReader( System.in ) );
		BufferedWriter writer = new BufferedWriter( new OutputStreamWriter( System.out ) );
		StringTokenizer token = new StringTokenizer( reader.readLine() );
		
		int M, V;
		Answer = "";
		N = Integer.parseInt( token.nextToken() ) + 1;
		M = Integer.parseInt( token.nextToken() );
		V = Integer.parseInt( token.nextToken() );
		
		adj = new boolean[ N ][ N ];
		visited = new boolean[ N ];

		for ( int m = 0; m < M; m++ ) {
			token = new StringTokenizer( reader.readLine() );
			int here = Integer.parseInt( token.nextToken() );
			int there = Integer.parseInt( token.nextToken() );
			adj[ here ][ there ] = true;
			adj[ there ][ here ] = true;
		}
		
		dfs( V );
		writer.write( Answer.substring(0, Answer.length() - 1 ) + "\n" );
		Answer = "";
		
		bfs( V );
		writer.write( Answer.substring(0, Answer.length() - 1 ) );
		writer.close();
		
	}
	
	public static void dfs( int here ) {
		Answer += here + " ";
		visited[ here ] = true;
		for ( int i = 0; i < N; i++ ) {
			if ( adj[ here ][ i ] && !visited[ i ]) {
				dfs( i );
			}
		}
	}

	
	public static void bfs( int v ) {
		Queue< Integer > Q = new PriorityQueue<Integer>();
		Arrays.fill( visited, false );
		
		Q.add( v );
		visited[ v ] = true;
		while( !Q.isEmpty() ) {
			int here = Q.poll();
			Answer += here + " ";
			for ( int i = 0; i < N; i++ ) {
				if ( adj[ here ][ i ] && !visited[ i ]) {
					Q.add( i );
					visited[ i ] = true;
				}
			}
		}
	}
	
}

bupjae 6년 전 1

다음과 같은 입력이 주어졌을 때, 올바른 BFS 순서는 "1 3 4 2"이지만 이 프로그램은 "1 3 2 4"를 출력합니다.

원래는 1과 연결되어 있는 3과 4를 먼저 방문해야 하지만, PriorityQueue 의 성질 때문에 3을 방문한 뒤 3에 연결되어 있는 2를 먼저 방문하게 됩니다.

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

문제

문제

출처

ICPC

[JAVA] 20% 이후에 실패가 됩니다.

ston13 6년 전 0

bupjae 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말