[백준] 5567번 : 결혼식 자바(JAVA) 풀이

문제

---

https://www.acmicpc.net/problem/5567 

---

문제 탐색하기

• n : 상근이 동기의 수
• m : 친구 관계 수
• a, b : 관계를 나타내는 값

 

• 상근이의 친구와 그 친구의 친구까지 초대하기 위해 depth 확인을 위해 DFS 이용
• 그래프는 인접리스트로 구현 / 인접리스트로 구현 시 양방향 그래프로 구현
• 상근이  depth = 0, 상근이 친구 depth = 1, 상근이 친구의 친구 depth = 2

 

가능한 시간복잡도

입력 범위 ( 2 ≤ n ≤ 500, 1≤ m ≤ 10000)

1. 인접리스트 초기화 : 시간 복잡도 O(n)
2. 그래프 생성 
   • n : 상근이 동기의 수 (그래프의 노드 수)
   • m : 친구 관계 개수 (그래프의 간선 수)
   • 관계를 입력받고 그래프를 구성할 때, m개의 간선을 입력받으므로 시간 복잡도 O(m)
3. DFS 탐색
   • 한 노드를 방문하고, 그 노드와 연결된 모든 간선을 탐색하므로 시간 복잡도 O(n + m)
4. 초대 가능한 사람 수 계산 : 시간 복잡도 O(n)
5. 전체 시간 복잡도 시간 복잡도 O(n + m)

 

---

헷갈렸던 부분

방문하지 않은 노드만 탐색하면 된다고 생각했는데 친구의 친구까지 탐색하기 위해 중복 탐색이 필요했다. 

if (!visited[next]) 조건 제거

1. 방문하지 않은 노드만 살펴보는 코드
2. 친구의 친구까지 탐색을 하려면 중복 방문을 허용해주어야하기 때문에 이 조건을 빼주어야 한다. 
3. 상근이와 친구가 공통으로 아는 친구가 있을 경우, 그 친구를 중복으로 방문하는 상황이 발생할 수 있다.

	static void dfs(int start, int level) {
		if(level == 2) { // 친구의 친구 보다 먼 관계일 때
			return;
		}
		
		for(int next:friend.get(start)) {
//			if(!visited[next]) {
				visited[next] = true;
				dfs(next, level+1);
				
//			}
		}
	}
}

---

코드 설계하기

• 입력받는 값을 인접리스트를 사용해 저장한다. (양방향으로 저장)
• 상근이(1번)을 시작으로 DFS 탐색을 시작한다. 
• level == 2 까지만 탐색하여 상근이의 친구의 친구까지만 방문한다.
• 탐색이 끝나면 visited 배열을 이용해 초대 가능한 사람(= 방문된 노드들)을 카운트한다.

---

풀이 코드

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 Main {
	
	static ArrayList<ArrayList<Integer>> friend;
	static boolean[] visited;
	static int count = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 상근이 동기의 수
		int m = Integer.parseInt(br.readLine()); // 관계 수
		
		visited = new boolean[n+1];
		visited[1] = true; // 상근이는 방문한 걸로 처리
		
		// 인접리스트로 관계저장 (DFS로 탐색할 수 있게)
		friend = new ArrayList<ArrayList<Integer>>();
		
		// 초기화
		for(int i=0;i<n+1;i++) {
			friend.add(new ArrayList<Integer>());
		}
		
		// 양방향 그래프로 저장
		for(int i=0;i<m;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
		
			friend.get(a).add(b);
			friend.get(b).add(a);
			
		}
		
        // 상근이부터 탐색 시작
		dfs(1,0);
		
        // 방문한 친구들만 카운트
		for(int i=2;i<n+1;i++) {
			if(visited[i]) {
				count++;
			}
		}
		System.out.println(count);

	}
	
	static void dfs(int start, int level) {
		if(level == 2) { // 친구의 친구 보다 먼 관계일 때
			return;
		}
		
		for(int next:friend.get(start)) {
				visited[next] = true;
				dfs(next, level+1);
		}
	}
}