다른 블로그를 많이 참고했다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.*; | |
| import java.io.*; | |
| /** | |
| * BOJ 2188 축사 배정 | |
| */ | |
| class Main { | |
| private static boolean visited[]; | |
| private static int edges[][], N, M, B[]; | |
| public static void main(String[] args) throws IOException{ | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); | |
| String str1[] = br.readLine().split(" "); | |
| N = Integer.parseInt(str1[0]); | |
| M = Integer.parseInt(str1[1]); | |
| edges = new int[N+1][M+1]; | |
| visited = new boolean[N+1]; | |
| B = new int[N+1]; | |
| for(int i = 1; i<=N; i++){ | |
| String str2[] = br.readLine().split(" "); | |
| int length = Integer.parseInt(str2[0]); | |
| Arrays.fill(edges[i], -1); | |
| for(int j = 1; j<=length; j++){ | |
| edges[i][j] = Integer.parseInt(str2[j]); | |
| } | |
| } | |
| int result = 0; | |
| for(int i = 1; i<=N; i++){ | |
| Arrays.fill(visited, false); | |
| if(dfs(i)) result++; | |
| } | |
| bw.write(String.valueOf(result)); | |
| bw.flush(); | |
| } | |
| private static boolean dfs(int start){ | |
| visited[start] = true; | |
| for(int i = 1; i<=M; i++){ | |
| if(edges[start][i] == -1) break; | |
| int v = edges[start][i]; | |
| if(B[v] == 0 || (!visited[B[v]] && dfs(B[v]))){ | |
| B[v] = start; | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| } |
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 10250 ACM 호텔 풀이 (0) | 2017.11.12 |
|---|---|
| BOJ 백준 1011 Fly me to the Alpha Centauri 풀이 Raw (0) | 2017.11.12 |
| BOJ 10803 풀이 (1) | 2017.11.06 |
| BOJ 10800 컬러볼 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 고등부 2번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 4번) (0) | 2017.11.02 |
| BOJ 10797 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 1번) (0) | 2017.10.27 |