목차
문제 정보
https://www.acmicpc.net/problem/5107
5107번: 마니또
N명의 사람들이 있다. 이들은 각자 다른 한 명의 이름이 적힌 쪽지를 받아서, 그 사람에게 몰래 선행을 베푼다. 이때 자기 자신의 이름을 받을 수는 없으며, 선행을 받은 사람은 누가 자신을 도와
www.acmicpc.net
난이도 : S1
유형 : Cycle Disjoint-Set, DFS, Hash
문제 풀이
해쉬맵을 이용하여 입력으로 주어지는 사람 이름에 고유한 번호를 부여해 준다.
사람이름 두 개가 입력될 때마다 고유한 번호 두 개를 얻어낸 다음 연결하여 그래프를 구성하면 된다.
방문하지 않은 곳을 차례대로 DFS 탐색을 진행한다.
만약 탐색 로직 실행 중 이미 탐색했던 곳을 만난다면 순열을 이루는 것이니 결과에 더해주면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;
/**
* BOJ_5107
* author_devteo77
*/
public class Main {
int T;
int N;
int res;
HashMap<String, Integer> map;
ArrayList<Integer>[] edges;
boolean[] isVisited;
public void execDFS(int cur) {
for (int next : edges[cur]) {
if (isVisited[next]) {
res++;
return;
}
isVisited[next] = true;
execDFS(next);
}
}
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
T = 1;
while (true) {
N = Integer.parseInt(br.readLine());
if (N == 0) {
break;
}
int number = 1;
map = new HashMap<>();
edges = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
edges[i] = new ArrayList<>();
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String from = st.nextToken();
String to = st.nextToken();
if (!map.containsKey(from)) {
map.put(from, number++);
}
if (!map.containsKey(to)) {
map.put(to, number++);
}
edges[map.get(to)].add(map.get(from));
}
res = 0;
isVisited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
if (!isVisited[i]) {
isVisited[i] = true;
execDFS(i);
}
}
sb.append(T++).append(" ").append(res).append('\n');
}
System.out.print(sb);
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
'Algorithm, Problem Solving > 백준(boj)' 카테고리의 다른 글
[백준][Java] 20920 - 영단어 암기는 괴로워 (0) | 2023.10.26 |
---|---|
[백준][Java] 6907 - Floor Plan (0) | 2023.10.19 |
[백준][Java] 23288 - 주사위 굴리기 2 (0) | 2023.10.12 |
[백준][Java] 17128 - 소가 정보섬에 올라온 이유 (1) | 2023.10.11 |
[백준][Java] 15240 - Paint bucket (0) | 2023.10.10 |
댓글