[C언어 백준 풀이] 2630번 : 색종이 만들기 (간단한 배열 탐색) (+ Solved.ac Class 3 획득)

이 포스트에서는 프로그래밍 문제 사이트인 백준 Online Judge의 Solved.ac 기준 Class 3의 문제에 해당하는 2630번 : 색종이 만들기 문제에 대한 풀이 코드와 해설을 다룹니다.

 

저는 사실 백준 티어를 크게 신경은 안 쓰고 있었지만 그래도 실력이 있는만큼 티어를 올려놓는 것도 나쁘지 않을 것 같아 Class 문제들을 해결해보고 있습니다.

 

이번 포스트에서는 Class 3을 취득하기 위한 마지막 문제로 간단한 탐색 문제를 풀어보도록 하겠습니다.

 

 

2630번 : 색종이 만들기

 

 

문제는 생략되었지만 간단히 요약하면 위와 같이 2^n 크기의 색종이가 주어졌을 때 이를 계속 반으로 나누면서, 해당 조각에 있는 색종이의 색이 모두 같을 경우 count 및 배제한다고 했을 때 최종적으로 색에 따라 count 되는 조각의 수가 몇 개인지 찾는 문제입니다.

 

 

예를 들어 위와 같은 예제 입력에 대해서, 오른쪽 아래 1/4 부분은 모두 1로 되어 있으므로 첫 번째 수행에서 나오는 1/4 조각은 파란색의 조각으로 count 되고 앞으로의 count에는 포함되지 않는다는 것입니다.

그렇게 해서 최종적으로 하얀색 조각의 수는 9, 파란색 조각의 수는 7이 되어 최종적으로 9와 7을 출력해주면 됩니다.

 

#include <stdio.h>

int N, arr[150][150] = {0, }, visit[150][150] = {0, }, temp, count_white = 0, count_blue = 0, check;

void check_block(int y, int x, int block) {
    check = 1;
    for(int i=y; i<y+block; i++)
        for(int j=x; j<x+block; j++)
            if(arr[i][j] != arr[y][x]) check = 0;
    if(check) {
        for(int i=y; i<y+block; i++)
            for(int j=x; j<x+block; j++) visit[i][j] = 1;
        if(arr[y][x]) count_blue++;
        else count_white++;
    }
}

int main() {
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) scanf("%d", &arr[i][j]);
    temp = N;
    while(temp) {
        for(int i=1; i<=N; i+=temp)
            for(int j=1; j<=N; j+=temp) {
                if(temp == 1 && !visit[i][j]) {
                    visit[i][j] = 1;
                    if(arr[i][j]) count_blue++;
                    else count_white++;
                }
                else if(!visit[i][j]) check_block(i, j, temp);
            }
        temp /= 2;
    }
    printf("%d\n%d", count_white, count_blue);
}

 

저는 DFS, BFS를 사용해야 하는 문제로 생각하고 접근했는데 그보다도 간단한 탐색 문제였습니다.

단순히 블럭에 대한 조건문을 세워주고, 한 블럭마다 visit 했었는지 그 여부를 확인하여 방문하지 않았다면 검사를 해주는 식으로 해나가면 됩니다.

블럭의 크기가 작아지는 것은 temp라는 변수에 N을 저장하고 while문에서 계속 2로 나눠주면서 반복시켜주면 됩니다.

모든 블럭의 색이 같은지는 check 변수를 이용해서 확인해주면 무난합니다.

 

---

 

결론적으로 위와 같이 Solved.ac에서 Class 3을 획득할 수 있었습니다.

앞으로는 너무 쉬운 문제들보다는 Class 4 문제들을 풀이하겠지만 시간이 남는다면 Class 3+의 에센셜 문제들도 풀이해보겠습니다.