[백준/boj] 17089: 세 친구 (Java) / 그래프

문제

17089번: 세 친구

풀이

A,B,C가 친구여야 한다는 점을 주의해야합니다! 이 점이 3중 for문 작성을 가능하게 하기 때문입니다. (친구가 아닌 경우 가지치기 가능)

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] friendMap = new int[N+1][N+1];
		int[] friend = new int[N+1];

		for(int i=0; i< M; i++) {
			st= new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			friendMap[A][B] = 1; // 1
			friendMap[B][A] = 1;
			friend[A]++; // 2
			friend[B]++;
		}
		
		int minNum = Integer.MAX_VALUE;
		for(int k=1; k<=N; k++) { // 3
			for(int i=1; i<=N; i++) {
				if(k == i || friendMap[k][i] != 1) continue; // 4
				for(int j=1; j<=N; j++) {
					int cnt = 0;
					if(j == i || j == k || friendMap[i][j] != 1 || friendMap[j][k] != 1) continue; // 5
					cnt += friend[i] - 2; // 6
					cnt += friend[j] - 2;
					cnt += friend[k] - 2;
					minNum = Math.min(cnt, minNum); // 7
				}
			}
		}
		if(minNum == Integer.MAX_VALUE) minNum = -1; // 8
		System.out.println(minNum); // 9
	}
}

예시 input

5 6
1 2
1 3
2 3
2 4
3 4
4 5

1. friendMap에 친구임을 1로 표시해줍니다. (양방향으로!)

friendMap	1	2	3	4	5
1	0	1	1	0	0
2	1	0	1	1	0
3	1	1	0	1	0
4	0	1	1	0	1
5	0	0	0	1	0

2. friend[A] 에는 A의 친구 수를 더해줍니다.

n	1	2	3	4	5
friend[n]	2	3	3	3	1

3. 세 친구이기 때문에 3중 for문을 사용합니다.

4. 이 때, k와 i가 같거나 둘이 친구가 아니라면 넘어갑니다. (가지치기)

5. k와 i는 친구여도, j가 이 둘 중 하나와 같거나 둘 중 하나와 친구가 아니라면 넘어갑니다. (가지치기)

6. 셋이 모두 친구라면 cnt 에 이들의 친구 수를 더합니다. 이때, 서로를 빼야 하므로 친구 수(friend) -2 해서 더합니다.

7. 최솟값을 계속해서 갱신합니다.

8. 만약 minNum이 Integer.MAX_VALUE라면 조건을 만족하지 못함을 의미합니다. minNum에 -1을 할당합니다.

9. minNum을 출력합니다.