[Java] 구름톤 챌린지 3주차 : 발전기 (2)

- 문제설명

 

- 해결과정

어제 풀었던 발전기 문제에서 심화된 문제이다.

아래와 같은 흐름으로 문제를 풀이했다.

• BFS를 돌면서 현재 그룹에서 이어진 집의 개수가 몇개인지 확인한다.
• 최종 이어진 개수가 K개 이상이라면 "단지"라고 판단해 리스트에 해당 번호를 추가한다.
• 배열을 전부 탐색해 가능한 모든 단지가 리스트에 담겼다면 요소를 하나씩 빼서 해시맵에 같은 유형의 단지가 몇 개씩 있는지 옮긴다.
• 완성된 해시맵을 순회하며 가장 단지 수가 많은 유형을 찾아 반환한다.

 

- 솔루션

import java.io.*;
import java.util.*;
class Main {
	private static int[][] town;
	private static boolean[][] visited;
	private static int[] dx = {-1, 1, 0, 0};
	private static int[] dy = {0, 0, -1, 1};
	private static ArrayList<Integer> list = new ArrayList<>(); 
	private static HashMap<Integer, Integer> map = new HashMap<>();
    
	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 K = Integer.parseInt(st.nextToken());
		town = new int[N][N];
		visited = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				town[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!visited[i][j]) {
					bfs(i, j, K);
				}
			}
		}

		for(Integer a : list) {
			map.put(a, map.getOrDefault(a, 0) + 1);
		}
		
		int maxCategory = 0;
		int maxCount = 0;
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			Integer key = entry.getKey();
			Integer value = entry.getValue();
			if(value > maxCount) {
				maxCategory = key;
				maxCount = value;
			}
			if(value == maxCount && key > maxCategory) {
				maxCategory = key;
			}
		}
		
		System.out.println(maxCategory);
	}
	
	private static void bfs(int curY, int curX, int K) {
		visited[curY][curX] = true;
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[]{curY, curX});
		int result = 1;
		while(!q.isEmpty()) {
			int[] xy = q.poll();
			for(int i = 0; i < 4; i++) {
				int nextX = xy[1] + dy[i];
				int nextY = xy[0] + dx[i];
				try {
					if(town[nextY][nextX] == town[curY][curX] && !visited[nextY][nextX]) {
						q.add(new int[]{nextY, nextX});
						visited[nextY][nextX] = true;
						result++;
					}
				} catch (ArrayIndexOutOfBoundsException e) {}
			}
		}
		if(result >= K) {
			list.add(town[curY][curX]);
		}
	}
}