[백준 / BOJ] 30206번 : 차량 배치 - JAVA

https://www.acmicpc.net/problem/30206

30206번: 차량 배치

경우의 수 구하기

조건과 설명만 읽고 복잡해보일 수 있지만, 사실 뜯어보면 간단하기 그지없는 문제이다. 모든 연결은 가중치 1을 갖기 때문에 BFS로 1번 도로와의 거리를 구할 수 있다. 1번 도로까지의 거리를 깊이 라고 하자. 어떤 도로에서도 충돌이 일어나면 안되기 때문에, 깊이가 같은 도로가 두 개 이상이라면 한 번에 그 중 하나에만 차량을 배치해야 한다.

 

각 깊이에 해당하는 도로의 개수를 모두 셌다면, 그 다음에는 경우의 수를 구해야 한다. 각 깊이에는 도로의 개수 + 1개의 경우의 수가 있다. 각 도로를 선택하는 경우 + 아무 것도 선택하지 않는 경우 가 있기 때문이다. 따라서 모든 깊이를 순회하며 (도로의 개수 + 1)을 total에 곱해준다.

 

단, 이렇게 계산하는 경우 어떤 도로에도 차량을 배치하지 않는 경우, 즉 배치된 차량이 0개인 경우가 생긴다. 조건에서 최소 한 대의 차량이 배치되어야 한다고 했으므로 total - 1을 해주어야 한다. 만일 공교롭게도 total이 0이었을 수도 있기 때문에, 1을 빼준 후 total이 음수가 된다면 1000000007을 한 번 더해주도록 한다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		List<Integer>[] list = new ArrayList[N];
		int[] cnt = new int[N];
		boolean[] v = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			list[i] = new ArrayList<>();
			cnt[i] = 1;
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken()) - 1;
			int end = Integer.parseInt(st.nextToken()) - 1;
			
			list[start].add(end);
			list[end].add(start);
		}
		
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[] {0, 0});
		v[0] = true;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			cnt[cur[1]]++;
			
			for (int i : list[cur[0]]) {
				if(v[i]) continue;
				v[i] = true;
				que.offer(new int[] {i, cur[1] + 1});
			}
		}
		
		long total = 1l;
		for (int i = 0; i < N; i++) {
			total *= cnt[i];
			total %= 1000000007;
		}
		if(--total < 0) total += 1000000007;
		System.out.println(total);
	}

}