반응형
5567번 결혼식
https://www.acmicpc.net/problem/5567
문제
상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.
출력
첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.
접근 방법 및 풀이
- 사람들의 관계를 양방향 인접리스트로 구현한다.
- 상근이 친구와 그 친구의 친구까지만 초대할 수 있기 때문에 cnt로 체크를 해야한다. (cnt = 0 : 상근이의 친구들, cnt = 1: 그 친구의 친구들 , cnt = 2 : 그 친구의 친구의 친구들)
- 방문가능한 노드는 방문 체크해주고, dfs 돌린 후 방문체크 배열에서 방문한 노드 개수 세주기
예제 1을 인접리스트로 구현하면 다음과 같다.
- 1 -> 2 -> 3
- 2 -> 1 -> 3
- 3 -> 1 -> 4 -> 3
- 4 -> 5
- 5 -> 4
- 6
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
static boolean[] visited;
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++) graph.add(new ArrayList<>());
visited = new boolean[N + 1]; //방문체크 배열
visited[1] = true;
StringTokenizer st;
for (int i = 0; i < M; i++) { // 양방향 인접리스트 구현
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
graph.get(from).add(to);
graph.get(to).add(from);
}
dfs(1, 0);
/**방문 가능한 노드 세주기*/
int answer = 0;
for (int i = 2; i < visited.length; i++) {// i = 1 : 상근이라 카운트X
if(visited[i]) answer++;
}
System.out.println(answer);
}
private static void dfs(int point, int cnt){
if(cnt == 2) { // 친구의 친구의 친구까지
return;
}
for(int i : graph.get(point)) {
visited[i] = true;
dfs(i, cnt+1);
}
}
}반응형
