백준 : 2617

https://www.acmicpc.net/problem/2617

2617번: 구슬 찾기

DFS

문제가 하도안풀리길래 질문 게시글을 보았다. 테스트 케이스중에 u v 가 같은 순환형 케이스가 존재한다는 것이다.

 

1이 1보다 크다 라는 말이 말이안되서 예외처리를 안햇는데 이것때문에 오랜 시간을 잡아 먹었다.

 

푸든 방법은 DAG 편방향 그래프를 그린다. 이때 아예 편방향 그래프를 In 그래프 Out 그래프 두가지를 만들거나

 

Out 그래프 하나만 만들어서 in out 수자를 세는 방법이 있다.

 

나는 out 그래프에서 시작하는 노드의 Out[n] 값을 노드에 도착할때마다 증가시키고

 

In[n] 그래프는 도착했으면 증가시키는 방향으로 In Out의 숫자를 카운팅 하였다.

 

package day0225;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class B2617 {
    static int N, M;
    static ArrayList<Integer> ver[];
    static int In[];
    static int Out[];
    static int n;
    static boolean visit[];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        In = new int[N + 1];
        Out = new int[N + 1];
 
        ver = new ArrayList[N + 1];
        for (int n = 1; n <= N; n++) {
            ver[n] = new ArrayList<Integer>();
        }
 
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
 
            ver[u].add(v);
        }
 
        for (n = 1; n <= N; n++) {
            visit = new boolean[N+1];
            visit[n] = true;
            int size = ver[n].size();
            for (int s = 0; s < size; s++) {
                if(visit[ver[n].get(s)])continue;
                Out[n]++;
                DFS(ver[n].get(s));
            }
 
        }
        
        int Answer = 0;
        int mid = (N+1)/2;
        for(n =1;n<=N;n++) {
            if(Out[n]>=mid) {
                Answer++;
            }else if( In[n] >=mid) {
                Answer++;
            }
        }
        System.out.println(Answer);
 
    }
 
    public static void DFS(int cur) {
        visit[cur] = true;
        In[cur]++;
        
        int size = ver[cur].size();
        for(int s=0;s<size;s++) {
            if(visit[ver[cur].get(s)])continue;
            Out[n]++;
            DFS(ver[cur].get(s));
        }
    }
}