[백준] 5567번: 결혼식(그래프, 구현)

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

5567번: 결혼식

코드

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

public class Main {
	public static int arr[][];		// 친구 관계
	public static boolean visit[];	// 방문 여부
	public static int n;	// 동기 수
	public static int m;	// 리스트 길이
	public static int count = 0;	// 초대할 친구 수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(bf.readLine());
		m = Integer.parseInt(bf.readLine());
		arr = new int[n+1][n+1];
		visit = new boolean[n+1];

		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a][b] = arr[b][a] = 1;	// 친구 관계 표시
		}

		for(int i=2; i<=n; i++) {
			if(arr[1][i] == 1) {	 // 상근이와 친구인 경우
				if(!visit[i]) {		 // 상근이와 친구인데 아직 방문하지 않은 경우
					count ++;		 // 초대
					visit[i] = true; // 방문 표시
				}

				// 상근이 친구의 친구 찾기 - 상근이와 연결된 정점에 연결되어 있는 정점 찾기.
				for(int j=2; j<=n; j++) {
					if(arr[i][j] == 1 && !visit[j]) {
						count ++;			// 상근이 친구의 친구도 초대
						visit[j] = true;	// 방문 표시
					}
				}
			}
		}

		System.out.println(count);
		bf.close();
	}

}

풀이

그래프 - 정점, 간선과 관련된 문제다.

문제의 예제를 그림으로 나타내면 아래와 같다.

 

 

위 그림에서 1번이 상근이고, 상근이는 친구와 친구의 친구 까지만 초대를 할 수 있다.

즉, 무방향 그래프(1->2 , 2->1)이며, 친구(간선) 와 친구의 친구(간선의 간선)인지 비교하며 초대한다.

상근이와 2번, 3번은 친구고 4번은 3번의 친구이기 때문에 친구(3)의 친구(4)여서 초대가 가능하지만,

5번과 6번은 관계가 없어서 초대를 할 수 없다.

따라서 초대할 수 있는 번호는 2, 3, 4 3명이다.

 

먼저 인접행렬을 구현한다.(dfs일줄 알고 static으로 변수들을 선언했다 ...)

번호는 1번부터 시작하므로 배열의 크기를 n+1로 잡는다.

		arr = new int[n+1][n+1];
		visit = new boolean[n+1];

		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a][b] = arr[b][a] = 1;	// 친구 관계 표시
		}

 

 

그 후 2번부터 상근이와 친구인지 판단한다.

반약 상근이와 친구인 경우(arr[1][i] == 1)

 - 그 친구는 초대하고 초대한 친구이므로 방문표시를 한다.

 - 그 후 친구의 친구를 판단해야 하므로, 이 친구와 연결되어있는 친구를 찾는다. (arr[i][j] == 1 && ! visit[j])

		for(int i=2; i<=n; i++) {
			if(arr[1][i] == 1) {	 // 상근이와 친구인 경우
				if(!visit[i]) {		 // 상근이와 친구인데 아직 방문하지 않은 경우
					count ++;		 // 초대
					visit[i] = true; // 방문 표시
				}

				// 상근이 친구의 친구 찾기 - 상근이와 연결된 정점에 연결되어 있는 정점 찾기.
				for(int j=2; j<=n; j++) {
					if(arr[i][j] == 1 && !visit[j]) {
						count ++;			// 상근이 친구의 친구도 초대
						visit[j] = true;	// 방문 표시
					}
				}
			}
		}

상근이의 친구와 친구(arr[i][j] == 1) 이고, 초대하지 않은 친구(방문표시가 되어 있지 않는 친구)인 경우,

그 친구까지 초대를 하고 방문 표시를 한다.