[백준] code.plus(브루트 포스 Part 1,JAVA)17089번, 세 친구

문제 링크

17089번: 세 친구

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. A, B, C 사람이 모두 친구여야 합니다.

2. A, B, C는 N명 중 임의의 3명을 선택한 사람들입니다.

3. A, B, C의 친구 수의 최소 합을 결과로 출력합니다.

4. 세 사람을 고를 수 없는 경우 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. A, B, C를 선택되는 모든 경우를 탐색하여 조건에 만족하면 친구 수의 합을 비교합니다.

 

3. 모든 경우를 탐색한 뒤에 친구 수 최소합을 결과로 출력합니다.

 

친구 조건.

 

A와 B와 C가 친구가 되려면

 

A - B

A - C

B - C

관계가 이루어지면 조건에 만족합니다.

 

※친구 수를 계산할 때 예외되는 경우는 6가지입니다.

(A-B), (B-A), (A-C), (C-A), (B-C), (C-B)

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 5, M = 6

친구 관계

(5, 6)
(1, 2)
(1, 3)
(2, 3)
(2, 4)
(3, 4)
(4, 5)

 

1 : 2, 3

2 : 1, 3, 4

3 : 1, 2, 4

4 : 2, 3, 5

5 : 4

 

2. A, B, C를 선택되는 모든 경우를 탐색하여 조건에 만족하면 친구 수의 합을 비교합니다.

 

1 2 3 : 친구 조건 O

1 : 2명

2 : 3명

3 : 3명

2 + 3 + 3 - 6 = 2

1 2 4 : 친구 조건 X
1 2 5 : 친구 조건 X

1 2 6 : 친구 조건 X
1 3 4 : 친구 조건 X
1 3 5 : 친구 조건 X

1 3 6 : 친구 조건 X
1 4 5 : 친구 조건 X

1 4 6 : 친구 조건 X

1 5 6 : 친구 조건 X
2 3 4 : 친구 조건 O

1 : 3명

2 : 3명

3 : 3명

3 + 3 + 3 - 6 = 3

2 3 5 : 친구 조건 X

2 3 6 : 친구 조건 X
2 4 5 : 친구 조건 X

2 4 6 : 친구 조건 X

2 5 6 : 친구 조건 X
3 4 5 : 친구 조건 X

3 4 6 : 친구 조건 X

3 5 6 : 친구 조건 X

4 5 6 : 친구 조건 X

 

3. 모든 경우를 탐색한 뒤에 친구 수 최소합을 결과로 출력합니다.

 

친구 수의 최소합 2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• search함수를 실행하여 N개중 A,B,C를 선택하는 모든 경우를 탐색합니다.
• 탐색 종료 후 친구 최소 수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 3중 for문을 이용하여 A,B,C를 선택하여 조건에 만족하는지 확인합니다.
• search함수는 조건에 만족할 때 친구 수를 구해서 최소값인지 확인합니다.

 

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

public class Main {
    static int N,M, answer = Integer.MAX_VALUE;
    static boolean[][] friend;	//친구 관계 저장 배열
    static int[] count;		//인물의 친구 수 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st= new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        friend = new boolean[N+1][N+1];
        count = 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());
            friend[a][b] = true;
            friend[b][a] = true;
            count[a]++;
            count[b]++;
        }
        //N명 중 A,B,C를 선택하는 모든 경우의 탐색하는 함수
        search();
        //조건에 만족하는 경우가 없을 때
        if(answer == Integer.MAX_VALUE)
            bw.write("-1");
        else
            bw.write(answer + "");	//최소합 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //N명 중 A,B,C를 선택하는 모든 경우 탐색 및 친구 최소 수 구하는 함수
    static void search(){
        for(int i=1;i<=N;i++){		//A선택
            for(int j=i+1;j<=N;j++){		//B선택
                if(friend[i][j]){		//A-B가 친구인지 확인
                    for(int s =j+1;s<=N;s++){		//C선택
                        if(friend[i][s] && friend[j][s])	//A-C, B-C 친구인지 확인
                            //최소수 구하기
                            answer = Math.min(answer,
                                    count[i] + count[j] + count[s] - 6);
                    }
                }
            }
        }
    }
}