백준 5567 - 결혼식(java)

www.acmicpc.net/problem/5567

5567번: 결혼식

1. 유형

그래프, 구현

 

2. 자료구조

양방향 인접리스트(arrayLIst배열)

 

3. 기능

- 인접리스트 만들기

- 재귀를 통해 깊이 2까지 탐색

- 탐색중 중복은 배제

 

4. 풀이

일단 인접리스트를 만든다.

그 후, 재귀를 통해 연결된 친구를 탐색.

다만 깊이가 3이 됐을때, return을 함.

 

코드

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

public class Main {
	static int N, M;
	static ArrayList<Integer> list[];
	static boolean visit[], friends[];
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		st = new StringTokenizer(in.readLine());
		M = Integer.valueOf(st.nextToken());
		list = new ArrayList[N+1];
		visit = new boolean[N+1];
		visit[1] = true;
		friends = new boolean[N+1];
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.valueOf(st.nextToken());
			int b = Integer.valueOf(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		recur(0, 1);
		int res=0;
		for(int i=2; i<=N; i++) {
			if(friends[i]) {
				res++;
			}
		}
		System.out.println(res);
	}
	static void recur(int depth, int num) {
		if(depth > 2) {
			return;
		}
		friends[num] = true;
		for(int k : list[num]) {
			if(!visit[k]) {
				visit[k] = true;
				recur(depth+1, k);
				visit[k] = false;
			}
		}
	}
}

5. 느낀점

오랜만에 푼 그래프 문제.

확실히 이런 인접리스트 문제가 많이 나오는것 같다.

확실하게 풀 수 있도록 계속 연습해야한다.