[백준-자바] N_2630 색종이 만들기

0woy·2024년 11월 3일

재귀

코딩테스트

목록 보기

34/39

📜 문제

문제는 위에서 자세히 설명했으므로 설명은 패스
그 정사각형인데, 숫자가 같아야 해요.

생각하기

예전에 풀었던 문제~ 그래두 확실히 하기 위해서 끄적거렸음

물구나무 서서도 재귀 문제라 쉽게 풀리겠지 생각했지만
내가 물구나무에 소질이 없어서 1시간 걸렸다.

접근 방식

먼저, 순회를 시작하기 전에 맨 처음 원소를 flag 변수로 잡고 시작
순회 하다가 flag랑 다른 애 나오면, 4분할을 해야 하잖아요?

위 처럼 길이가 4인 정사각형이 주어져있다고 했을 때,
현재 flag (1)과 다른 0을 만나면 우측 그림처럼 4분할해서 4번의 재탐색이 필요함.

4분할의 기점인 위치를 살펴보면,

위치	좌표
좌상단	(0,0)
우상단	(0,2)
좌하단	(2,0)
우하단	(2,2)

시작점이 (len=2)을 따른다는 사실을 알 수 있다.
이런 접근 방식을 가지고 코드를 짜면 됨

🍳 전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N_2630 {
    private static int res[];
    public static void recur(int [][] map,  int row, int col, int len){
        int flag =  map[row][col];
        if(len == 1){
            res[flag]++;
            return;
        }
        for(int i=row; i<row+len;i++){
            for(int j=col;j<col+len;j++){
                if(flag != map[i][j]){
                    int half = len/2;
                    recur(map, row,col, half);
                    recur(map, row,col+half, half);
                    recur(map, row+half,col, half);
                    recur(map, row+half,col+half, half);
                    return;
                }
            }
        }
        res[flag]++;
        return;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int [][] map  = new int[n][n];
        res = new int[2];
        for(int i=0;i<map.length;i++){
            StringTokenizer st  = new StringTokenizer(br.readLine());
            for(int j=0;j<map[0].length;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        recur(map, 0,0,n);
        System.out.println(res[0]+" "+res[1]);
    }
}

하나씩 살펴봅시다.

✍ 부분 코드 설명

입력

public class N_2630 {
    private static int res[];
    
    ...
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int [][] map  = new int[n][n];
        res = new int[2];
        for(int i=0;i<map.length;i++){
            StringTokenizer st  = new StringTokenizer(br.readLine());
            for(int j=0;j<map[0].length;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        recur(map, 0,0,n);
        System.out.println(res[0]+" "+res[1]);
    }
}

n: 초기에 주어지는 종이 크기
map: 배열 저장
res: 색종이 개수 저장

2차원 배열인 map에 입력으로 주어지는 초기 색종이 값 저장
recur 함수를 호출하여 탐색

recur 함수

 public class N_2630 {
    private static int res[];
    public static void recur(int [][] map,  int row, int col, int len){
        int flag =  map[row][col];
        if(len == 1){
            res[flag]++;
            return;
        }
        for(int i=row; i<row+len;i++){
            for(int j=col;j<col+len;j++){
                if(flag != map[i][j]){
                    int half = len/2;
                    recur(map, row,col, half);
                    recur(map, row,col+half, half);
                    recur(map, row+half,col, half);
                    recur(map, row+half,col+half, half);
                    return;
                }
            }
        }
        res[flag]++;
        return;
    }
    
    ...

recur 함수는 row, col 매개변수에 현재 종이의 flag가 될 시작점을 받고,
len에는 현재 종이의 길이를 받음

만일 len이 1인 경우에는 한 칸만 탐색하면 되기때문에,
res 배열의 flag 위치의 값을 1을 증가.

그 외의 경우 배열을 순회하며 flag와 다른 값을 마추진 경우 4분할을 다시 시작합니다.

여기서 row, col 값을 넘겨줄 때, 현재 인덱스 (i,j) 를 넘겨주는 실수를 했는데,
그렇게 넘겨주면 내가 원하는 곳이 아닌 엉뚱한 곳을 시작점으로 4분할 하게 되므로..
꼭 row, col을 넘겨줘야한다.

넘 당연한 소리 같지만, 나는 이게 발목을 좀 잡았다.

나는 이 코드의 핵심이 return이라고 생각한다.

왜냐하면 처음에 return이 아닌 break를 썼다가 색종이 개수가 280개인가 웃기지도 않은 숫자가 나왔다.

이중반복문이기 때문에, break를 써도 상위 반복문(현재 i)은 그대로 진행이 돼서
우리가 앞전에 4분할해서 탐색한 부분을 중복 탐색 하기 때문이다.

우리는 한 번 안 맞으면 더 안 볼 거잖아요?
그러려면 함수를 탈출하는 return을 작성해줘야 원하는 로직으로 프로그램이 동작합니다.