구름톤 챌린지 13일차 - 발전기(2)

https://level.goorm.io/exam/195695/%EB%B0%9C%EC%A0%84%EA%B8%B0-2/quiz/1

구름LEVEL

 

import java.util.*;

class Houses{
	int x;
	int y;
	public Houses(int i,int j){
		this.x = i;
		this.y = j;
	}
}

class Main {
		public static int N; // 마을의 크기
    public static int K; // 단지의 기준
    public static int[][] building; //마을
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {-1, 1, 0, 0};
    public static boolean[][] visited;
    public static int count;
    public static Queue<Houses> queue = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        building = new int[N][N];
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) { // 마을에 숫자 채워넣기
            for (int j = 0; j < N; j++) {
                building[i][j] = sc.nextInt();
            }
        }

        // 단지 갯수 구하기
        int maxbuildingtype = 0; // 최대 건물 유형 번호
        int[] checkK = new int[31]; // 단지 갯수
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j]) { // 이미 체크했다면 다시 안 해야 함
                    continue;
                }else{
                    count = 0; // 단지 내 건물 개수 초기화
                    maxbuildingtype = Math.max(maxbuildingtype, building[i][j]); // 최대 건물 유형 번호 계산
                    bfs(i, j, building[i][j]);
                    if (count >= K) { // 만약 단지 내 건물 개수가 K보다 크거나 같다면
                        checkK[building[i][j]]++; // 건물 유형 번호 단지 개수 추가
                    }
                }

            }
        }

        // 최대 단지를 가진 건물 유형 번호 찾기
        int max = -1;
        int answer = 0;
        for (int i = 1; i <= maxbuildingtype; i++) {
            if (checkK[i] >= max) {
                max = checkK[i];
                answer = i;
            }
        }

        System.out.println(answer);
    }

    public static void check ( int x, int y, int c){ // x,y는 위치 c는 건물 유형 번호
        if (building[x][y] != c || visited[x][y]) {
            return;
        }
        visited[x][y] = true;
        count++;
        for (int i = 0; i < 4; i++) {
            int posX = x + dx[i];
            int posY = y + dy[i];
            if (posX >= 0 && posX < N && posY >= 0 && posY < N) {
                check(posX, posY, c);
            }
        }
    }

    public static void bfs ( int x, int y, int c){
        queue.add(new Houses(x, y));
        while (!queue.isEmpty()) {
            Houses houses = queue.poll();
            for (int k = 0; k < 4; k++) {
                Houses nexthouse = new Houses(houses.x + dx[k], houses.y + dy[k]);
                if (nexthouse.x >= 0 && nexthouse.x < N && nexthouse.y >= 0 && nexthouse.y < N && !visited[nexthouse.x][nexthouse.y] && building[nexthouse.x][nexthouse.y] == c) {
                    queue.add(nexthouse);
                    visited[nexthouse.x][nexthouse.y] = true;
                    count++;
                }
            }
        }
    }
	
}

 

실수한거 못찾고 계속 FAIL 떠서 정말 그만둘 뻔 했다. 알고보니 너무 어이없는 실수였다. 하나는 for문 범위였고 하나는 count++를 빼먹었었다.

이번 문제도 아무생각없이 dfs로 풀었다가 맨 마지막 케이스 런타임에러 나는거 보고 bfs로 바꿨다. 탐색 문제를 계속 풀다보니까 이 유형 문제가 나온다면 할 수 있겠는데?라는 생각이 든다.