PS/BaekJoon

2630 JAVA ์ƒ‰์ข…์ด ๋งŒ๋“ค๊ธฐ

chaerlo127 2024. 2. 1. 02:36
728x90

Sliver 2. ์ƒ‰์ข…์ด ๋งŒ๋“ค๊ธฐ

 

๐Ÿ€ ๋ฌธ์ œ

์•„๋ž˜ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ™์ด ์—ฌ๋Ÿฌ๊ฐœ์˜ ์ •์‚ฌ๊ฐํ˜•์นธ๋“ค๋กœ ์ด๋ฃจ์–ด์ง„ ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ์ข…์ด๊ฐ€ ์ฃผ์–ด์ ธ ์žˆ๊ณ , ๊ฐ ์ •์‚ฌ๊ฐํ˜•๋“ค์€ ํ•˜์–€์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๊ฑฐ๋‚˜ ํŒŒ๋ž€์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๋‹ค. ์ฃผ์–ด์ง„ ์ข…์ด๋ฅผ ์ผ์ •ํ•œ ๊ทœ์น™์— ๋”ฐ๋ผ ์ž˜๋ผ์„œ ๋‹ค์–‘ํ•œ ํฌ๊ธฐ๋ฅผ ๊ฐ€์ง„ ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ํ•˜์–€์ƒ‰ ๋˜๋Š” ํŒŒ๋ž€์ƒ‰ ์ƒ‰์ข…์ด๋ฅผ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค.


์ „์ฒด ์ข…์ด์˜ ํฌ๊ธฐ๊ฐ€ N×N(N=2k, k๋Š” 1 ์ด์ƒ 7 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜) ์ด๋ผ๋ฉด ์ข…์ด๋ฅผ ์ž๋ฅด๋Š” ๊ทœ์น™์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

์ „์ฒด ์ข…์ด๊ฐ€ ๋ชจ๋‘ ๊ฐ™์€ ์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ์ง€ ์•Š์œผ๋ฉด ๊ฐ€๋กœ์™€ ์„ธ๋กœ๋กœ ์ค‘๊ฐ„ ๋ถ€๋ถ„์„ ์ž˜๋ผ์„œ <๊ทธ๋ฆผ 2>์˜ I, II, III, IV์™€ ๊ฐ™์ด ๋˜‘๊ฐ™์€ ํฌ๊ธฐ์˜ ๋„ค ๊ฐœ์˜ N/2 × N/2์ƒ‰์ข…์ด๋กœ ๋‚˜๋ˆˆ๋‹ค. ๋‚˜๋ˆ„์–ด์ง„ ์ข…์ด I, II, III, IV ๊ฐ๊ฐ์— ๋Œ€ํ•ด์„œ๋„ ์•ž์—์„œ์™€ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋ชจ๋‘ ๊ฐ™์€ ์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ์ง€ ์•Š์œผ๋ฉด ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ๋˜‘๊ฐ™์€ ํฌ๊ธฐ์˜ ๋„ค ๊ฐœ์˜ ์ƒ‰์ข…์ด๋กœ ๋‚˜๋ˆˆ๋‹ค. ์ด์™€ ๊ฐ™์€ ๊ณผ์ •์„ ์ž˜๋ผ์ง„ ์ข…์ด๊ฐ€ ๋ชจ๋‘ ํ•˜์–€์ƒ‰ ๋˜๋Š” ๋ชจ๋‘ ํŒŒ๋ž€์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๊ฑฐ๋‚˜, ํ•˜๋‚˜์˜ ์ •์‚ฌ๊ฐํ˜• ์นธ์ด ๋˜์–ด ๋” ์ด์ƒ ์ž๋ฅผ ์ˆ˜ ์—†์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•œ๋‹ค.

์œ„์™€ ๊ฐ™์€ ๊ทœ์น™์— ๋”ฐ๋ผ ์ž˜๋ž์„ ๋•Œ <๊ทธ๋ฆผ 3>์€ <๊ทธ๋ฆผ 1>์˜ ์ข…์ด๋ฅผ ์ฒ˜์Œ ๋‚˜๋ˆˆ ํ›„์˜ ์ƒํƒœ๋ฅผ, <๊ทธ๋ฆผ 4>๋Š” ๋‘ ๋ฒˆ์งธ ๋‚˜๋ˆˆ ํ›„์˜ ์ƒํƒœ๋ฅผ, <๊ทธ๋ฆผ 5>๋Š” ์ตœ์ข…์ ์œผ๋กœ ๋งŒ๋“ค์–ด์ง„ ๋‹ค์–‘ํ•œ ํฌ๊ธฐ์˜ 9์žฅ์˜ ํ•˜์–€์ƒ‰ ์ƒ‰์ข…์ด์™€ 7์žฅ์˜ ํŒŒ๋ž€์ƒ‰ ์ƒ‰์ข…์ด๋ฅผ ๋ณด์—ฌ์ฃผ๊ณ  ์žˆ๋‹ค.


์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ์ข…์ด์˜ ํ•œ ๋ณ€์˜ ๊ธธ์ด N๊ณผ ๊ฐ ์ •์‚ฌ๊ฐํ˜•์นธ์˜ ์ƒ‰(ํ•˜์–€์ƒ‰ ๋˜๋Š” ํŒŒ๋ž€์ƒ‰)์ด ์ฃผ์–ด์งˆ ๋•Œ ์ž˜๋ผ์ง„ ํ•˜์–€์ƒ‰ ์ƒ‰์ข…์ด์™€ ํŒŒ๋ž€์ƒ‰ ์ƒ‰์ข…์ด์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

๐Ÿ€ ์ž…๋ ฅ

์ฒซ์งธ ์ค„์—๋Š” ์ „์ฒด ์ข…์ด์˜ ํ•œ ๋ณ€์˜ ๊ธธ์ด N์ด ์ฃผ์–ด์ ธ ์žˆ๋‹ค. N์€ 2, 4, 8, 16, 32, 64, 128 ์ค‘ ํ•˜๋‚˜์ด๋‹ค. ์ƒ‰์ข…์ด์˜ ๊ฐ ๊ฐ€๋กœ์ค„์˜ ์ •์‚ฌ๊ฐํ˜•์นธ๋“ค์˜ ์ƒ‰์ด ์œ—์ค„๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ๋งˆ์ง€๋ง‰ ์ค„๊นŒ์ง€ ์ฃผ์–ด์ง„๋‹ค. ํ•˜์–€์ƒ‰์œผ๋กœ ์น ํ•ด์ง„ ์นธ์€ 0, ํŒŒ๋ž€์ƒ‰์œผ๋กœ ์น ํ•ด์ง„ ์นธ์€ 1๋กœ ์ฃผ์–ด์ง€๋ฉฐ, ๊ฐ ์ˆซ์ž ์‚ฌ์ด์—๋Š” ๋นˆ์นธ์ด ํ•˜๋‚˜์”ฉ ์žˆ๋‹ค.

๐Ÿ€ ์ถœ๋ ฅ

์ฒซ์งธ ์ค„์—๋Š” ์ž˜๋ผ์ง„ ํ–์–€์ƒ‰ ์ƒ‰์ข…์ด์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ๋‘˜์งธ ์ค„์—๋Š” ํŒŒ๋ž€์ƒ‰ ์ƒ‰์ข…์ด์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ€ ์˜ˆ์ œ

์˜ˆ์ œ์ž…๋ ฅ

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

์˜ˆ์ œ์ถœ๋ ฅ

9
7

๐Ÿ€  ์„ฑ๊ณต ๊ณผ์ •

์ ‘๊ทผํ•˜๊ธฐ ์–ด๋ ค์›Œ ๋ ˆํผ๋Ÿฐ์Šค๋ฅผ ์ฐพ์•„๋ณด๋ฉฐ ๋ฌธ์ œ๋ฅผ ์ ‘๊ทผํ–ˆ๋‹ค.

๋ฌธ์ œ ์ ‘๊ทผ

์ƒ‰์ข…์ด๊ฐ€ ํ•˜๋‚˜์˜ ์ƒ‰์œผ๋กœ ์ด๋ฃจ์–ด ์žˆ์ง€ ์•Š๋‹ค๊ณ  ํŒ๋‹จ์ด ๋˜๋ฉด ๋ฐ˜์œผ๋กœ ์ ‘๊ณ , ๋‹ค์‹œํ™•์ธํ•˜๊ณ  ๋ฐ˜์œผ๋กœ ์ ‘๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
๋ฐ˜๋ณต์ ์ธ ๊ณผ์ •๋“ค์€ ํ•จ์ˆ˜๋ฅผ ์ƒ์„ฑํ•˜์—ฌ ์žฌ๊ท€๋กœ ํ˜ธ์ถœํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•œ๋‹ค.

๋”ฐ๋ผ์„œ
1. ํ•˜๋‚˜์˜ ์ƒ‰(ํฐ์ƒ‰ or ํŒŒ๋ž€์ƒ‰)์œผ๋กœ ์ด๋ฃจ์–ด์ ธ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ์ฝ”๋“œ
2. ๋ฐ˜์œผ๋กœ ์ ‘์–ด(์‚ฌ์ด์ฆˆ๋ฅผ ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆ ) ๋‹ค์‹œ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ์ฝ”๋“œ
๋กœ ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๋‹ค.

์„ฑ๊ณต ์ฝ”๋“œ

import java.io.*;
import java.util.*;

public class Main{
    public static int[][] arrays;
    public static int white = 0;
    public static int blue = 0;

    public static void main(String[] args) throws Exception {
        // ์ž…๋ ฅ ๊ฐ’
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Integer n = Integer.parseInt(br.readLine());
        arrays = new int[n][n];
        for (int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n ; j++){
                arrays[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // ์ถœ๋ ฅ ๊ฐ’
        partition(n, 0, 0);
        System.out.println(white);
        System.out.println(blue);
    }

    public static void partition(int n, int x, int y){
        // ๊ฐ’์ด ์ฑ„์›Œ์ ธ ์žˆ๋Š” ๊ฒฝ์šฐ
        if(checkColor(n, x, y)){
            if(arrays[x][y] == 0) white++;
            else blue++;
            return;
        }

        // ์ฑ„์›Œ์ ธ ์žˆ์ง€ ์•Š์€ ๊ฒฝ์šฐ
        n = n / 2; // ๊ฐ’์„ ์ ˆ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆ„๊ธฐ
        partition(n, x, y); // 4์‚ฌ๋ถ„๋ฉด
        partition(n, x + n, y); // 1์‚ฌ๋ถ„๋ฉด
        partition(n, x, y + n); // 2์‚ฌ๋ถ„๋ฉด
        partition(n, x + n, y + n); // 3์‚ฌ๋ถ„๋ฉด
    }

    public static boolean checkColor(int n, int x, int y){
        int check = arrays[x][y];
        for(int i = x ; i < n + x; i++){
            for (int j = y; j < n + y; j++){
                if(arrays[i][j] != check) return false;
            }
        }
        return true;
    }
}
728x90