글 읽기 - 1260번 질문드립니다!

reiui9 8년 전 0

말이좀 헷갈려서

BFS 두가지방법으로 구현해봤는데 전부 틀렸다고 나오네요 ㅠ ㅠ

제가 케이스만들고 그려서 해봐도 자꾸틀렸다고...

도와주세요 ~

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
class Main {
	public static int[][] Node;
	public static int N,M;
	public static int[] check;
	public static Queue q;
    
	public static void receive(Scanner sc){
		Node = new int[N+1][N+1];
		for(int i=0;i<=N;i++)
			for(int j=0;j<=N;j++)
				Node[i][j]=0;
		for(int i=0;i<M;i++){
			Node[sc.nextInt()][sc.nextInt()]=1;
		}
	}
	public static void printArr(int[][] arr){
		for(int i=0;i<=N;i++){
			for(int j=0;j<=N;j++)
				System.out.print(arr[i][j]+" ");
			System.out.println();}
	}
	public static void DFS(int[] check,int start){
		System.out.print(start);
		check[start]=1;
		for(int i=0;i<=N;i++){
			if(Node[start][i]==1 && check[i]==0){
				System.out.print(" ");
				DFS(check,i);
			}
		}
	}
	
	public static void BFS(int[] check,int start){
		int head=0,tail=0;
		q.add((int)start);
		System.out.println();
		System.out.print(start);
		do{
			start=(int)q.remove();
			for(int i=0;i<=N;i++){
				if(Node[start][i]==1 && check[i]==0){
					q.add(i);
					check[i]=1;
					System.out.print(" "+i);
				}
			}
		}while(!q.isEmpty());
		System.out.println();
	}
	
	/*
	public static void BFS(int[] check,int start){
		ArrayList arr1 = new ArrayList();
		ArrayList arr2 = new ArrayList();
		int count=0;
		arr1.add(start);
		check[start]=1;
		System.out.println();
		do{
			
			if(count == 0 && arr1.isEmpty()) {count=1; continue;}
			else if(count==0){
				Collections.sort(arr1);
				start=(int)arr1.remove(0);
				System.out.print(start);
			}
			if(count==1 && arr2.isEmpty()) {count=0; continue;}
			else if(count==1){
				Collections.sort(arr2);
				start=(int)arr2.remove(0);
				System.out.print(start);
			}
			for(int i=0;i<=N;i++){
				
				if(Node[start][i]==1 && check[i]==0){
					if(count==0){
						arr2.add(i);
						check[i]=1;
					}
					else if(count==1){
						arr1.add(i);
						check[i]=1;
					}
				}
				
			}
		if(!arr1.isEmpty() || !arr2.isEmpty()) System.out.print(" ");
		}while(!arr1.isEmpty() || !arr2.isEmpty());

	}
	*/
	public static void main(String args[]) throws FileNotFoundException{
		//Scanner sc = new Scanner(new FileInputStream("C://input//Beak_input.txt"));
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		int start = sc.nextInt();
		check = new int[N+1];
		q = new PriorityQueue<Integer>();
		
		receive(sc);
		
		for(int i=0;i<=N;i++){
			check[i]=0;
		}
		DFS(check,start);
		
		for(int i=0;i<=N;i++){
			check[i]=0;
		}
		BFS(check,start);
	}
}

Nada 8년 전 0

3가지 문제점을 해결하니 정답이 나왔네요.

문제점들은 다음과 같습니다.

1. 우선 양방향 간선이 주어집니다.

따라서 Node[sc.nextInt()][sc.nextInt()] = 1이 아니라

int a = sc.nextInt(), b = sc.nextInt(); Node[a][b]=1; Node[b][a]=1

로 수정하셔야 합니다.

2. BFS부분에서 초기 start를 출력했음에도 check[초기 start] = 1을 해주는 과정이 없습니다.

때문에 초기 start를 while문 안에서 다시 한번 queue에 넣는 경우가 발생할 수 있습니다.

3. priority_queue 사용의 문제점

편의상 BFS를 탐색했을 때 (NODE 번호, 깊이)를 한 데이터라 가정하고

BFS의 특징은 깊이가 작은 것부터 순차적으로 접근해 나가야 합니다.

하지만 priority_queue를 사용했을 경우

( NODE 번호 = 2, depth = 3 ) , ( NODE 번호 = 1, depth = 4 ) 일 경우 어떤 것이 먼저 POP이 될까요?

깊이가 4이지만 NODE 번호가 작은 1번 노드가 먼저 나오게 됩니다.

따라서 이 때부터 BFS 탐색이 되지 못하게 됩니다.

때문에 priority_queue 대신에 그냥 queue를 사용하시면 해결됩니다.

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

문제

문제

출처

ICPC

1260번 질문드립니다!

reiui9 8년 전 0

Nada 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말