[Baekjoon] 5107_마니또

Silver I

문제(출처: https://www.acmicpc.net/problem/5107)

---

< 마니또 >

 

문제 풀이 

 

각 관계를 배열로 저장한 후 연결 고리를 찾는다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class _5107_ { // 마니또
	static boolean visited[];
	static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n;
		int cnt = 1;
		while ((n = Integer.parseInt(bf.readLine())) != 0) {
			ArrayList<String> list = new ArrayList<>();
			visited = new boolean[n];
			arr = new int[n];

			for(int i=0; i<n; i++) {
				st = new StringTokenizer(bf.readLine());
				String a = st.nextToken();
				String b = st.nextToken();

				if (!list.contains(a)) {
					list.add(a);
				}
				if (!list.contains(b)) {
					list.add(b);
				}
				arr[list.indexOf(a)] = list.indexOf(b);	
			}

			int result = 0;
			for (int i = 0; i < n; i++) {
				if (!visited[i]) {
					visited[i] = true;
					result += 1;

					search(i);
				}
			}
			bw.write(cnt++ + " " + result + "\n");
		}
		bw.flush();
	}

	private static void search(int num) {
		if (!visited[arr[num]]) {
			visited[arr[num]] = true;
			search(arr[num]);
		}
	}
}

변수)
n : 사람의 명수
cnt : 케이스 번호
list : 사람 번호
visited : 방문 여부
arr : 마니또 관계
a, b : 두 사람의 이름
result : 연결 고리의 개수

 

사람의 명수가 0이 아닐 때까지 다음 과정을 반복한다.

 

1) 사람의 수만큼 두 사람의 이름을 입력받아 마니또 관계를 저장한다. 이때 이름을 입력받은 것을 편하게 저장하기 위해 ArrayList에 먼저 저장해 index 번호로 관리한다. arr배열에 list의 index 번호로 마니또 관계를 저장한다.

2) 아직 방문하지 않은 사람들을 방문하여 연결 고리 개수를 구하기 위해 search 함수를 호출한다.

3) 해당 케이스 번호와 연결 고리의 개수를 출력한다.

 

search(index)

마니또의 마니또를 아직 방문하지 않았다면 방문 후 search 함수를 호출한다.

---

---