[백준/java] 17089. 세 친구

문제 링크 - https://www.acmicpc.net/problem/17089

🌱 문제

---

🌱 풀이

• 어떻게 풀어야 할지 막막했던 문제이다.
• 처음에 생각한 방법은 다음과 같다.

1. N Combination 3 연산을 통해 3명을 선택한다.
2. 그 3명이 서로 친구인지 확인한다.
3. 서로 친구라면 A의 친구 수 + B의 친구 수 + C의 친구 수의 최솟값으로 정답 변수를 갱신한다.

• 3번의 시도 끝에 겨우 맞았는데 위에 적은 1번 단계에서 어떤 방식으로 N명중에 3명을 선택할 것인지와 2번 단계에서 3명이 서로 친구인지 확인하는 과정이 시간초과를 판가름했다.
  (결국 다 신경써야했다는 ..? )

---

1번째 시도

• 단순하게 처음 든 생각으로 N Combination 3으로 3명을 선택했다. N의 범위가 (3 ≤ N ≤ 4,000) 이었는데 단순하게 그렇게 큰 숫자가 아니라고 생각했다.
• 하지만 4000 Combination 3을 하는순간 약 9자리 수 만큼 커지기 때문에 당연하게도 시간초과가 났다.
• 게다가 고른 3명이 친구인지 확인하는 과정에도, 친구정보를 ArrayList<Integer>[]배열에 저장한다음 list[x].contains(y)를 통해서 x와 y가 친구인지 확인했는데, 해당 연산도 O(N)의 시간복잡도가 들기 때문에 무조건 시간초과가 나는 코드였다.
  (최악의 경우, 약 O(NxNxNxNxNxN) 인 셈 ....?)

public static void comb(int cnt,int start) {
		if(cnt==3) {
			if(isFriend()) { // 3명이 서로 친구이면 최솟값으로 answer 갱신 
				answer=Math.min(answer, list[numbers[0]].size()+ list[numbers[1]].size()+list[numbers[2]].size()-6);
			}
			return;
		}
		
		for(int i=start; i<=M; i++) {
			numbers[cnt]=i;
			comb(cnt+1, i+1);
		}
		
	}
	
	public static boolean isFriend() { // 3명이 친구관계인지 확인하는 함수
		if(list[numbers[0]].contains(numbers[1]) && list[numbers[1]].contains(numbers[2])&& list[numbers[0]].contains(numbers[2]))
			return true;
		else
			return false;
			
	}

---

2번째 시도

• 1번째 시도한 방법에서 N combination 3의 시간을 줄이기 위해 콤비네이션 대신 다른방법을 시도했다.
• 친구 관계를 ArrayList<Info>()에 저장 한 후, 해당 정보들을 돌면서 새로운 1명만 골라서 친구관계인지 확인을 해주었다.
• 이 방법은 O(NxN)이라고 생각해서 통과가 될 줄 알았지만 여전히 시간초과였다.
• 틀리고 나서 생각해보니 여전히 친구관계인지 확인할때 list[x].contains(y)를 이용하여 확인했기 때문에 O(NxNxNxNxN) 정도가 되버려서 시간초과가 났다.....

for(int i=0; i<infos.size();i ++) {
	Info cur = infos.get(i);
	for(int j=1; j<=N; j++) {
		if(j==cur.x || j==cur.y) // N명중 이미 고른 2명은 패스 
			continue;
				
		if(isFriend(cur.x, cur.y, j)) {
			answer=Math.min(answer, list[cur.x].size()+list[cur.y].size()+list[j].size()-6);
		}
	}
}

---

3번째 시도

• ArrayList의 contains()로 발생하는 O(N)의 시간복잡도를 줄이기 위해 ArrayList가 아니라 Set 자료구조를 이용했다.
• 2번째 시도와 방법은 거의 같고, 3명이 서로 친구인지 확인할 때 set[x].contains(y)를 이용했다.
• 또한 2번째 시도와 3번째 시도는 3명중에 두명이 이미 친구관계임을 확인하고 나서 나머지 한명을 확인하기 때문에 contains를 3번이 아니라 2번만 해주면 된다.
• set의 contains()는 O(1)이기 때문에 세번째 코드의 총 시간복잡도는 약 O(NxNx1x1)이 되어서 매우 충분할 것이라고 예상된다.

  for(int i=0 ;i<M; i++) {
	st = new StringTokenizer(br.readLine());
	int x= Integer.parseInt(st.nextToken());
	int y=Integer.parseInt(st.nextToken());
	set[x].add(y); // set배열에 친구 정보 저장 
	set[y].add(x);
	infos.add(new Info(x, y));
			
}

/// x와 y가 서로 친구임은 알고있는 상태이므로 (x,j), (y,j) 가 각각 서로 친구인지만 확인해주면 됨.
	public static boolean isFriend(int x, int y, int j) {
		if(set[x].contains(j) && set[y].contains(j)) // set.contains()의 시간복잡도: O(1)
			return true;
		else
			return false;
			
	}

---

🌱 정답 코드

package Dec_week04;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

//17089. 세 친구
public class boj_17089 {
	static class Info{
		int x;
		int y;
		public Info(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
	
	static int N,M;
	static Set<Integer> set[];
	static ArrayList<Info> infos;
	static int answer=Integer.MAX_VALUE;
	static int numbers[];
	static int totalCnt;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		
		numbers=new int[3];
		set = new HashSet[N+1];
		infos= new ArrayList<Info>();
		
		
		// list배열 초기화
		for(int i=0; i<=N; i++) {
			set[i]=new HashSet<Integer>();
		}
		
		for(int i=0 ;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x= Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			set[x].add(y); // set배열에 친구 정보 저장 
			set[y].add(x);
			infos.add(new Info(x, y));
			
		}
		
		for(int i=0; i<infos.size();i ++) { // 주어진 친구 관계 수 만큼 반복
			Info cur = infos.get(i); 
			for(int j=1; j<=N; j++) {
				if(j==cur.x || j==cur.y) // N명중 이미 고른 2명은 패스 
					continue;
				
				if(isFriend(cur.x, cur.y, j)) { // 3명이 친구라면 최솟값으로 갱신
					answer=Math.min(answer, set[cur.x].size()+set[cur.y].size()+set[j].size()-6);
				}
			}
		}
	
		if(answer==Integer.MAX_VALUE)
			answer=-1;
		
		System.out.println(answer);
		
	}

	
	public static boolean isFriend(int x, int y, int j) {
		if(set[x].contains(j) && set[y].contains(j)) // set.contains()의 시간복잡도: O(1)
			return true;
		else
			return false;
			
	}

}

---

틀린 코드 1

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

//17089. 세 친구
public class Main {
	
	static int N,M;
	static ArrayList<Integer> list[];
	static int answer=Integer.MAX_VALUE;
	static int numbers[];
	static int totalCnt;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		
		numbers=new int[3];
		list = new ArrayList[N+1];
		
		// list배열 초기화
		for(int i=0; i<=N; i++) {
			list[i]=new ArrayList<Integer>();
		}
		
		for(int i=0 ;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x= Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			list[x].add(y);
			list[y].add(x);
		}
		comb(0,1);
		if(answer==Integer.MAX_VALUE)
			answer=-1;
		
		System.out.println(answer);
		
	}
	public static void comb(int cnt,int start) {
		if(cnt==3) {
			if(isFriend()) {
				answer=Math.min(answer, list[numbers[0]].size()+ list[numbers[1]].size()+list[numbers[2]].size()-6);
			}
			return;
		}
		
		for(int i=start; i<=M; i++) {
			numbers[cnt]=i;
			comb(cnt+1, i+1);
		}
		
	}
	
	public static boolean isFriend() {
		if(list[numbers[0]].contains(numbers[1]) && list[numbers[1]].contains(numbers[2])&& list[numbers[0]].contains(numbers[2]))
			return true;
		else
			return false;
			
	}

}

---

틀린 코드 2

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

import javax.sound.sampled.DataLine.Info;

//17089. 세 친구
public class Main {
	static class Info{
		int x;
		int y;
		public Info(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
	
	static int N,M;
	static ArrayList<Integer> list[];
	static ArrayList<Info> infos;
	static int answer=Integer.MAX_VALUE;
	static int numbers[];
	static int totalCnt;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		
		numbers=new int[3];
		list = new ArrayList[N+1];
		infos= new ArrayList<Info>();
		
		
		// list배열 초기화
		for(int i=0; i<=N; i++) {
			list[i]=new ArrayList<Integer>();
		}
		
		for(int i=0 ;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x= Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			list[x].add(y);
			list[y].add(x);
			infos.add(new Info(x, y));
			
		}
		
		for(int i=0; i<infos.size();i ++) {
			Info cur = infos.get(i);
			for(int j=1; j<=N; j++) {
				if(j==cur.x || j==cur.y)
					continue;
				
				if(isFriend(cur.x, cur.y, j)) {
					answer=Math.min(answer, list[cur.x].size()+list[cur.y].size()+list[j].size()-6);
				}
			}
		}
	
		if(answer==Integer.MAX_VALUE)
			answer=-1;
		
		System.out.println(answer);
		
	}

	
	public static boolean isFriend(int a, int b, int c) {
		if(list[a].contains(b) && list[b].contains(c)&& list[a].contains(c))
			return true;
		else
			return false;
			
	}

}