문제
지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.
A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.
입력
첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.
출력
첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.
예제 입력 1
3
NYY
YNY
YYN
예제 출력 1
2
예제 입력 2
3
NNN
NNN
NNN
예제 출력 2
0
1. BFS
BFS를 이용해 풀었다. graph에 직접 친구 관계를 저장하고, N명을 모두 BFS를 돌면서 2-친구 수를 찾도록 했다.
BFS에서는 우선 직접 친구를 큐에 넣고, 큐를 돌면서 방문 체크하며 2-친구까지 찾도록 했다. 친구의 친구 까지만 2-친구 이므로, 큐에 노드를 다시 넣는 과정은 필요없다.
import java.io.*;
import java.util.*;
public class Main {
static int N;
static List<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(); // 직접 친구 관계 담을 리스트
static int answer = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<>());
}
// 직접 친구 관계 저장
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
if (s.charAt(j) == 'Y') {
graph.get(i).add(j);
}
}
}
for (int i = 0; i < N; i++) {
BFS(i);
}
bw.write(answer + "");
bw.flush();
bw.close();
br.close();
}
public static void BFS(int start) {
Queue<Integer> que = new LinkedList<>();
boolean[] ch = new boolean[N];
int tmp = 0; // 2-친구 수
ch[start] = true;
for (int i : graph.get(start)) {
que.offer(i);
tmp++;
ch[i] = true;
}
while (!que.isEmpty()) {
int friend = que.poll();
for (int friend_2 : graph.get(friend)) {
if (!ch[friend_2]) {
ch[friend_2] = true;
tmp++;
}
}
}
answer = Math.max(answer, tmp);
}
}
메모리 | 시간 |
14400 KB | 140 ms |
2. 구현
BFS 없이 구현으로 풀어보았다. 아래처럼 풀면 최악의 경우 O(N^3) 이므로 BFS로 풀었을 때 보다 시간이 많이 걸렸다.
우선 직접 친구 관계를 담을 list, 2-친구 관계를 담을 friend 리스트 변수를 준비한다.
list에는 받아온 값 즉 직접 친구 관계를 저장하고, 직접 친구의 친구를 돌면서 2-친구를 찾는 과정을 N번 만큼 반복해 friend에 값을 넣어주었다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
List<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); // 직접 친구 관계 담을 리스트
List<HashSet<Integer>> friend = new ArrayList<HashSet<Integer>>(); // 2-친구 관계 담을 리스트
for (int i = 0; i < N; i++) {
list.add(new ArrayList<>());
friend.add(new HashSet<>());
}
// 직접 친구 관계 저장
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
if (s.charAt(j) == 'Y') {
list.get(i).add(j);
}
}
}
// 2-친구 관계 찾기
for (int i = 0; i < N; i++) {
for (int j : list.get(i)) { // i의 직접 친구
friend.get(i).add(j);
for (int k : list.get(j)) { // i의 2-친구
friend.get(i).add(k);
}
}
}
int answer = 0;
for (int i = 0; i < N; i++) {
answer = Math.max(answer, friend.get(i).size());
}
if (answer > 0) answer -= 1; // 자기 자신은 제외이므로 -1
bw.write(answer + "");
bw.flush();
bw.close();
br.close();
}
}
메모리 | 시간 |
16300 KB | 176 ms |
'6. 자료구조 & 알고리즘 > 6-2. 백준' 카테고리의 다른 글
백준 - [ 1051: 숫자 정사각형 ] (0) | 2023.07.29 |
---|---|
백준 - [ 1049번: 기타줄 ] (0) | 2023.07.29 |
백준 - [ 11657: 타임머신 ] (0) | 2023.07.29 |
백준 - [ 1520: 내리막 길 ] (0) | 2023.07.28 |
백준 - [ 1024번: 수열의 합 ] (0) | 2023.07.22 |