(Graph)Wedding

문제 설명

접근 방법 - 친구 관계를 리스트로 구현했다. - 1의 인접노드와 1의 인접노드의 인접노드 갯수만 세주기 때문에 BFS/DFS는 불필요하다.

틀린 이유 초대할 친구를 카운팅할 때 중복 체크(방문 체크)를 해주어야하는데 해주지 않았다.

Solution 우리는 1번의 친구 i와 i의 친구만 관심있기 때문에 2차원 배열로 관계를 저장하는 것이 좋다고 할 수 있다!!!🌟 =>arr[1][i] == 1: 친구 초대 if(!v[i]) 이면 i초대. arr[i][j] == 1 && !v[j] : 친구의 친구 초대 1. 2차원 배열에 친구 관계 저장한다. arr[i][j] : i와 j가 친구.(의미해석이 더 직관적이다!) arr[1][i] = 1 : 1과 i가 친구라는 의미! i번 친구를 초대하면 i번 친구 j도 초대하므로 arr[i][j] = 1이면 j도 초대한다!

2. 이미 초대한 친구인지 확인하기 위해 boolean 배열 필요! 초대하기 전에 중복체크하고 난 후에 해준다!

느낀 점 리스트로 구현하는 것보다 이 문제의 경우 2차원 배열로 친구 관계를 저장해서 처리해주는 것이 더 빠르고 간결한 것 같다.

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

public class Wedding_2nd {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		int[][] friends = new int[n+1][n+1];
		boolean[] visit = new boolean[n+1];
		//간선 갯수만큼 친구관계 저장!
		for(int i=0;i<m;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			friends[u][v] = 1;
			friends[v][u] = 1;
		}
		
		int cnt=0;
		for(int i=2;i<=n;i++) {
			if(friends[1][i]==1) {
				if(!visit[i]) {
					visit[i] = true;
					cnt++;
				}
				
				for(int j=2;j<=n;j++) {
					if(friends[i][j] == 1 && !visit[j]) {
						visit[j] = true;
						cnt++;
					}
				}
			}
		}
		System.out.println(cnt);
	}

}

1의 친구 초대하는 부분에서 if(friends[1][i] == 1 && !visit[i]) 이렇게 조건문을 걸어서 i를 초대하면 될것 같지만 아니다. 왜냐하면 이 조건문은 아래에 i의 친구도 초대하는 부분도 포함하는 조건문인데 조건문을 저렇게 걸어버리면 1의 친구 2초대(visit[2] = true) 2의 친구 3초대(visit[3] = true) 1의 친구 3 차례에서 3은 초대하지 않더라도 3의 친구 4(친구의 친구)를 초대하는 부분은 실행되어야하는데 2가지 조건을 만족하지 않아 전체가 실행되지 않아서 오답이 나오게 된다!

for(int i=2;i<=n;i++) {
			if(friends[1][i]==1) {
				if(!visit[i]) {
					visit[i] = true;
					cnt++;
				}
				
				for(int j=2;j<=n;j++) {
					if(friends[i][j] == 1 && !visit[j]) {
						visit[j] = true;
						cnt++;
					}
				}
			}
		}