[백준 1298] 노트북의 주인을 찾아서 (JAVA)
문제
풀이
이분 매칭을 이용하여 해결할 수 있습니다.
초기값이 이렇게 되어있는 경우
- 1번 사람이 1번 노트북을 지목합니다.
- 2번 사람이 1번을 노트북을 지목합니다.
- 1번 사람은 1번 노트북 다음 3번 노트북을 지목합니다.
- 3번 사람이 1번 노트북을 지목합니다.
- 2번 사람은 1번 노트북 다음 2번 노트북을 지목합니다.
만약에 3번 사람이 1번 노트북을 지목했을 때 2번 사람이 다음 지목할 노트북이 없으면 3번이 다음 노트북을 지목합니다.(다음 노트북이 없으면 지목을 못합니다.)
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int[] occupy;
public static boolean[] visited;
public static ArrayList<Integer>[] myNotebook;
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());
visited = new boolean[N + 1];
occupy = new int[N + 1];
myNotebook = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
myNotebook[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
myNotebook[Integer.parseInt(st.nextToken())].add(Integer.parseInt(st.nextToken()));
}
int ans = 0;
for (int i = 1; i <= N; i++) {
Arrays.fill(visited, false);
if (dfs(i)) ans++;
}
System.out.println(ans);
br.close();
}
public static boolean dfs(int num) {
for (int i = 0; i < myNotebook[num].size(); i++) {
int notebookNum = myNotebook[num].get(i);
if (visited[notebookNum]) continue;
visited[notebookNum] = true;
if (occupy[notebookNum] == 0 || dfs(occupy[notebookNum])) {
occupy[notebookNum] = num;
return true;
}
}
return false;
}
}
Author And Source
이 문제에 관하여([백준 1298] 노트북의 주인을 찾아서 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@solser12/백준-1298-노트북의-주인을-찾아서-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)