[BOJ] 17834 사자와 토끼 (JAVA)

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

17834번: 사자와 토끼

그래프를 홀짝으로 칠해보는 것이 핵심인 문제입니다.

BFS나 DFS를 이용하여 해결할 수 있습니다.

 

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		
		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());
		int[] odd  = new int[N + 1];
		int[] even = new int[N + 1];
		ArrayList<Integer>[] list = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		} // end of input
		
		Queue<Integer> q = new LinkedList<>();
		q.offer(1);
		odd[1] = 1;
		int time = 0;
		
		while(!q.isEmpty()) {
			
			time++;
			int size = q.size();
			
			while(size-- > 0) {
				
				int now = q.poll();
				
				for (int a : list[now]) {
					
					if(time % 2 == 0 && odd[a] == 0) {
						
						odd[a] = time + 1;
						q.offer(a);
						
					} else if(time % 2 == 1 && even[a] == 0){

						even[a] = time + 1;
						q.offer(a);
					}
					
				}
				
			}
			
		}
		
		int cntEven = 0;
		int cntOdd = 0;
		
		for (int i = 1; i <= N; i++) {
			
			if(even[i] == 0) cntEven++;
			else cntOdd++;
			
		}
		
		System.out.println(2 * cntEven * cntOdd);
		
	}
	
}