난이도 : S2
Link : https://www.acmicpc.net/problem/5567
Tag : 그래프, BFS
문제 탐색하기
- 친구 관계가 주어진다.
- 상근이의 친구의 친구까지 초대한다.
- 초대할 사람의 수를 구하여라
시도 1 ( 성공😲)
떠오른 문제 해결 방법
여기서 핵심은 친구의 친구까지만 초대한다는 것이었습니다.
bfs를 이용하여 방문하되 ,depth가 2이하인 노드의 개수를 구하면 된다고 생각하였습니다.
시간복잡도⏰
BFS의 시간복잡도 O(V + E)이므로 시간 제한 1초안에 충분히 해결할 수 있습니다.
n (2 ≤ n ≤ 500)
m (1 ≤ m ≤ 10000)
구현 방법
세부 구현 사항
1. 주어진 값을 입력받는다.
2. depth 배열을 생성한후 -1로 모두 초기화한다.
3. 1을 큐에 넣고, depth[1] = 0 으로 초기화한다.
4. bfs 과정을 진행한다.
4-1. 큐에서 해당 숫자를 꺼낸다.
4-2. 해당 숫자의 친구인 숫자들을 꺼낸다.
4-3. 하나씩 친구들을 확인한다. 이때, depth가 -1이 아닐경우 이미 방문했기 때문에 다음 친구로 넘어간다.
4-4. 첫 방문일 경우, 큐에 해당 친구를 넣는다. 그리고 depth는 큐에서 꺼낼때의 친구(num)의 depth에 1을 더해서 넣는다.
5. depth가 2이하, 0이상인 것들의 개수를 센다. (-1일경우 연관관계가 아에 없는 사람임)
전체코드
import java.io.IOException;
import java.io.*;
import java.util.*;
class Main {
private static int n;
private static int m;
private static List<List<Integer>> friendship = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
for (int i = 0; i <= n; i++) {
friendship.add(new ArrayList<Integer>());
}
StringTokenizer st;
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
friendship.get(s).add(e);
friendship.get(e).add(s);
}
int[] depth = new int[n + 1];
Arrays.fill(depth, -1);
Queue<Integer> queue = new ArrayDeque<>();
queue.add(1);
depth[1] = 0;
while (!queue.isEmpty()) {
int num = queue.poll();
List<Integer> friends = friendship.get(num);
for (int friend : friends) {
if (depth[friend] != -1) {
continue;
}
queue.add(friend);
depth[friend] = depth[num] + 1;
}
}
int count = 0;
for (int i = 2; i <= n; i++) {
// System.out.println(depth[i]);
if (depth[i] <= 2 && depth[i] >= 0) {
count++;
}
}
System.out.println(count);
}
}
마무리
BFS, 그래프등은 단골 문제이므로 많이 연습하자.
댓글