> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/implementation/graph-wedding.md).

# (Graph)Wedding

**문제 설명**

![](/files/-McrAIAe3TtUsO1mkuct)

**접근 방법**\
\- 친구 관계를 리스트로 구현했다.\
\- 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차원 배열로 친구 관계를 저장해서 처리해주는 것이 더 빠르고 간결한 것 같다.

```java
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가지 조건을 만족하지 않아 전체가 실행되지 않아서 오답이 나오게 된다!**

```java
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++;
					}
				}
			}
		}
```