[BOJ] 세 친구 - 17089번

이나영·2021년 12월 24일
0

알고리즘

목록 보기
12/17
post-thumbnail

🌠"세 친구" - 17089번 G5

🎃문제설명

👨‍👦‍👦N명의 사람이 있고, 여기서 세 사람 A, B, C를 고르려고 한다. 세 사람은 모두 친구여야 한다.

세 사람을 고르는 방법은 매우 많이 있을 수 있다. 이때, A의 친구 수 + B의 친구 수 + C의 친구 수가 최소가 되어야 한다. 친구 수의 합을 계산할 때, 세 사람은 빼고 계산해야 한다. 즉, A의 친구 수를 계산할 때, B와 C는 빼고 계산해야 하고, B의 친구 수를 계산할 때는 A와 C, C의 친구 수를 계산할 때는 A와 B를 빼고 계산해야 한다.


입력

첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친구라는 것을 의미한다.

사람은 1번부터 N번까지 번호가 매겨져 있다. 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.


출력

첫째 줄에 A의 친구 수 + B의 친구 수 + C의 친구 수의 최솟값을 출력한다. 만약, 문제 조건대로 세 사람을 고를 수 없는 경우에는 -1을 출력한다.


💾입출력 예

입력출력
5 6
1 2
1 3
2 3
2 4
3 4
4 5
2
7 4
2 1
3 6
5 1
1 7
-1

알고리즘 분류

  • 그래프 이론

🌟문제 이해 및 풀이계획

✏️생각없이 N3N^3으로 N명의 친구들 중에 3명을 뽑아 모든 경우의 수를 시도하려 했다.

✏️당연히 시간초과가 났다..


✍🏻내 코드1 - 오답코드

package BOJ;

import java.util.Scanner;

/*
 * 2021.12.25 daily algo/commit
 * 
 * Brute Force, Combination
 */

public class boj_17089 {
	
	static int min = 4000;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] friends = new int[N+1][N+1];
		boolean[] visited = new boolean[N+1];
		
		for(int i=0; i<M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			friends[a][b] = friends[b][a] = 1;
		}
		
		sc.close();
		
		int[] select = new int[3];
		combination(friends, visited, select, N, 3, 0);
		
		if(min == 4000) System.out.println(-1);
		else System.out.println(min);
	}
	
	public static void combination(int[][] friends, boolean[] visited, int[] select, int n, int r, int start) {
		if(r == 0) {
			// 선택한 세 사람이 모두 친구일 때
			if(friends[select[0]][select[1]] == 1 && friends[select[0]][select[2]] == 1 && friends[select[1]][select[2]] == 1) {
				int num = 0;
				for(int i=0; i<3; i++) {
					for(int j=1; j<=n; j++) {
						// 세사람 본인은 빼고 친구 수 계산
						if(j != select[0] && j != select[1] && j != select[2] && friends[select[i]][j] == 1) {
							num += 1;
						}
					}
				}
				if(num < min) min = num;
			}
			return;
		}
		for(int i=start; i<n; i++) {
			visited[i] = true;
			select[3-r] = i+1;
			combination(friends, visited, select, n, r-1, i+1);
			visited[i] = false;
		}
	}
}

✏️일단, 모든 경우를 검사하기엔 많으니 한명을 잡고 2명 이상 연결되어 있는 경우만 검사하면 된다고는 생각했는데 로직을 어떻게 처리해야할지 머리가 복잡해서 잘 돌아가지 않았다..


강의내용

✔️시간복잡도 : N3N^3 = 400034000^3 = 64,000,000,000 (너무크다)

✔️A, B, C의 친구를 검사하기 위해서 3중 for문을 이용한다.

⚔️3중 for문을 이용하여 친구 관계의 유무(간선)의 정보를 저장해놓은 이차원 배열에서 관계가 있는 것들만 체크하고 친구 수를 체크하고 최소값을 비교한다.


✍🏻내 코드2 + 강의

package BOJ;

import java.util.Scanner;

/*
 * 2021.12.25 daily algo/commit
 * 
 * Brute Force
 */

public class boj_17089_2 {
	
	static int min = 4000;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] friends = new int[N+1][N+1];
		
		for(int i=0; i<M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			friends[a][b] = friends[b][a] = 1;
		}
		
		sc.close();
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				// A, B가 친구일 때
				if(friends[i][j] == 1) {
					for(int k=1; k<=N; k++) {
						if(friends[j][k] == 1 && friends[k][i] == 1) {
							int cnt = count(friends, i, j, k, 0);
							if(min > cnt) min = cnt;
						}
					}
				}
			}
		}
		
		if(min == 4000) System.out.println(-1);
		else System.out.println(min);
	}
	
	public static int count(int[][] friends, int a, int b, int c, int cnt) {
		for(int j=1; j<friends.length; j++) {
			// 세 친구가 관계있는 모든 친구의 수
			if(friends[a][j] == 1) cnt += 1;
			if(friends[b][j] == 1) cnt += 1;
			if(friends[c][j] == 1) cnt += 1;
		}
		return cnt - 6; // 세 친구x3 빼주기
	}
}

💡조합으로 모든 경우를 구하지 않고, 관계가 있는(이차원 배열의 요소 값이 1인) 경우를 타고 타고 넘어가서 선택한 세 명이 친구인지 아닌지 체크하고 친구가 맞다면 친구의 수를 구할 수 있다.

profile
소통하는 백엔드 개발자로 성장하기

0개의 댓글