[백준] 5567. 결혼식 (자바 JAVA)

[ 문제 ] [백준] 5567. 결혼식 (자바 JAVA)

문제 링크 :https://www.acmicpc.net/problem/5567

5567번: 결혼식

---

# 접근 방법 및 풀이

 

• 와 정말 문제 제대로 안 읽고 아무생각없이 풀면 틀리기 너무너무 좋은 문제다. 충격..
• 인접리스트와 dfs로 구현했다. bfs로도 할 수 있지만 dfs를 선택했다.
• 여기서 상근이 친구와 그친구의 친구까지만 초대할 수 있기 때문에 depth 체크를 해야한다.
• 그리고 인접리스트로 구현시 양방향 그래프로 구현해야한다.
• 여기까지는 잘 했는데, 인접리스트로 구현 후에 노드 방문체크 배열 boolean check[ ]만들고, 해당 노드를 방문하면 check[i] = true해주고, 방문하지 않은 노드만 살펴보면 되는 줄 알고 구현했는데 14퍼에서 계속 틀렸다.
• 방문하지 않은 노드만 살펴보는게 아니라 방문가능한 노드는 방문 체크해주고 dfs돌린 후에 방문 체크 배열에서 방문한 노드 갯수만 세주면 되는 거였다.
• 근데 처음에 이걸 이해하지 못해서 예제 1번으로 다시 살펴봤는데, depth도 잘못 체크하고 있었다. depth를 3까지 봤는데 2로 해야한다. depth = 0일 때 상근이의 친구들, depth = 1일때 그친구의 친구들 depth = 2는 친구의 친구의 친구가 되기 때문이다.
• 예제 1을 인접리스트로 구현하면 다음과 같다.
• 1 -> 2 -> 3
• 2 -> 1 -> 3
• 3 -> 1 -> 4 -> 2
• 4 -> 5
• 5 -> 4
• 6
• 여기서 이미 방문한 노드를 또 방문하더라도, depth 2안에서 가능한 노드만 방문한 것이기 때문에 dfs가 끝난 후에 check[] 에 true인 노드 개수만 세어주면 된다. 그리고 check는 2부터 봐야한다. 1은 상근이 자신이기때문이다.

 

# 주의할 점

 

• 상근이 친구와 친구의 친구만 초대 가능하다.
• 양방향 그래프로 구현해야함.
• depth와 방문체크 배열 확인

 

JAVA 코드

package Silver;

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

public class bj5567_결혼식 {
	static int n, answer = 0;
	static boolean check[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(in.readLine());
		int m = Integer.parseInt(in.readLine());
		List<Integer> list[] = new ArrayList[n + 1];
		for (int i = 1; i < list.length; i++) {
			list[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		check = new boolean[n + 1];
		check[1] = true;
		dfs(1, list, 0);
		for (int i = 2; i < check.length; i++) {
			if(check[i]) answer++;
		}
		System.out.println(answer);
	}

	private static void dfs(int num, List<Integer>[] list, int depth) {
		if (depth == 2) {
			return;
		}
		for (int i = 0; i < list[num].size(); i++) {
			int next = list[num].get(i);
			check[next] = true;
			dfs(next, list, depth + 1);
		}
	}
}

REVIEW

어처구니 없는 실수하지말자.. 문제 정확히 이해하고 설계하고 풀자!
실전에서 만나면 무작정 풀고 왜 안돼? 이러지말고...