프로그래머스 쿼드 압축 후 세기

쿼드 압축 후 세기 : programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

주어진 Map을 나누어 1의 영역의 갯수와 0의 영역의 갯수를 구하는 문제이다.

최초 나는 굳이 해당 문제를 bfs로 풀려고 했다.

하지만 풀고 나서보니 굳이 bfs를 안써도 되는 문제 였다 ㅠㅠ

 

코드에 대하여 설명하자면 

먼저 bfs로 같은 정사각형내의 숫자가 같은지 판별한다.

한약 정사각형 내의 숫자가 다를 경우 limit을 절반씩 반감하며 왼쪽 대각선 위, 오른쪽 대각선 위, 왼쪽 대각선 아래, 오른쪽 대각선 아래를

따로 구해준다.

만일 정사각형 내의 숫자가 같을 경우 해당 정사각형의 기준이되는 숫자를 보고 해당 숫자를 증가시켜준다

import java.util.*;
class Solution {
    public int[] movY = { -1, 0, 1, 0 };
    public int[] movX = { 0, 1, 0, -1 };
    public int[] answer = new int[2];

    public int[] solution(int[][] arr) {

        int len = arr.length;

        bfs(arr, 0, 0, len, arr[0][0]);
        return answer;
    }

    public void bfs(int[][] map, int startY, int startX, int limit, int num) {
        boolean[][] visit = new boolean[limit][limit];
        Queue<int[]> q = new LinkedList<int[]>();

        q.add(new int[] { startY, startX });
        while (!q.isEmpty()) {
            int len = q.size();
            for (int l = 0; l < len; l++) {
                int[] arr = q.poll();

                for (int i = 0; i < 4; i++) {
                    int newY = arr[0] + movY[i];
                    int newX = arr[1] + movX[i];

                    if (outOfBound(newX - startX, newY - startY, limit) || visit[newX - startX][newY - startY]) {
                        continue;
                    }

                    if (num == map[newY][newX]) {
                        visit[newX - startX][newY - startY] = true;
                        q.add(new int[] { newY, newX });
                    } else {
                        bfs(map, startY, startX, limit / 2, map[startY][startX]);
                        bfs(map, startY + limit / 2, startX, limit / 2, map[startY + limit / 2][startX]);
                        bfs(map, startY, startX + limit / 2, limit / 2, map[startY][startX + limit / 2]);
                        bfs(map, startY + limit / 2, startX + limit / 2, limit / 2,
                                map[startY + limit / 2][startX + limit / 2]);
                        return;
                    }
                }
            }
        }

        answer[map[startY][startX]]++;
        return;

    }

    public boolean outOfBound(int x, int y, int limit) {
        if (x < 0 || x >= limit || y < 0 || y >= limit) {
            return true;
        }
        return false;
    }
}

로직은 같지만 bfs를 안쓰고 풀경우 찔끔더 빨랐다;;ㅠ 

import java.util.*;
class Solution {
  public int[] answer = new int[2];

	public int[] solution(int[][] arr) {
		int len = arr.length;
		bfs(arr, 0, 0, len);
		return answer;
	}

	public void bfs(int[][] map, int startY, int startX, int limit) {

		int num = map[startY][startX];

		for (int i = startY; i < startY + limit; i++) {
			for (int j = startX; j < startX + limit; j++) {
				if (num != map[i][j]) {
					for (int k = 0; k < 2; k++) {
						for (int l = 0; l < 2; l++) {
							bfs(map, startY + k * (limit / 2), startX + l * (limit / 2), limit / 2);
						}
					}
					return;
				}
			}
		}

		answer[map[startY][startX]]++;
		return;

	}
}