글 읽기 - 도대체 어떤 예외 케이스가 있는건가요?

filot 7년 전 0

문제 자체는 쉽다고 했는데

통과율이 낮은걸로 봐서는 특이 케이스가 있을꺼라 생각했는데

역시나네요..

근데 아무리 생각해봐도.. 딱히 잘못된게 없어 보이는데... 신기하네요..

기본 로직은

1. 인접리스트 구성

2. 인접리스트 정렬

3. dfs

4. bfs

입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static int M;
    static int S;
    static List[] adjList;
    
    static BufferedReader reader;
    static PrintWriter writer;
 
    public static void main(String[] args) throws Exception {    	
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 
        StringTokenizer st = new StringTokenizer(reader.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
         
        adjList = new List[N + 1];
         
        for (int i = 1; i <= N; i++)
            adjList[i] = new ArrayList<Integer>();
         
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(reader.readLine());
             
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
             
            adjList[u].add(v);
        }
        
        for (int i = 1; i <= N; i++)
        	Collections.sort(adjList[i]);
        
        boolean[] isVisited = new boolean[N + 1];
   		dfs(S, isVisited);
        
   		writer.println();
   		
        bfs();
        
        writer.close();
        reader.close();
    }
    
    public static void dfs(int u, boolean[] isVisited) {
    	isVisited[u] = true;
    	writer.print(u + " ");
    	
    	List<Integer> list = adjList[u];
    			
		for (Integer v : list)
			if (!isVisited[v])
				dfs(v, isVisited);
    }
    
    public static void bfs() {
    	boolean[] isVisited = new boolean[N + 1];
    	Queue<Integer> QUEUE = new ArrayDeque<Integer>();
    	
    	isVisited[S] = true;
    	writer.print(S + " ");
    	QUEUE.offer(S);
    	
    	while (!QUEUE.isEmpty()) {
    		Integer u = QUEUE.poll();
    		
    		List<Integer> list = adjList[u];
    		
    		for (Integer v : list) {
    			if (!isVisited[v]) {
    				isVisited[v] = true;
    				writer.print(v + " ");
    				QUEUE.offer(v);
    			}
    		}
    	}
    }
}

filot 7년 전 0

간선이 주어지면 이게 양방향이군요...

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

문제

문제

출처

ICPC

도대체 어떤 예외 케이스가 있는건가요?

filot 7년 전 0

filot 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말