๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/2630
- ์๋ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ์ฌ๋ฌ๊ฐ์ ์ ์ฌ๊ฐํ์นธ๋ค๋ก ์ด๋ฃจ์ด์ง ์ ์ฌ๊ฐํ ๋ชจ์์ ์ข ์ด๊ฐ ์ฃผ์ด์ ธ ์๊ณ , ๊ฐ ์ ์ฌ๊ฐํ๋ค์ ํ์์์ผ๋ก ์น ํด์ ธ ์๊ฑฐ๋ ํ๋์์ผ๋ก ์น ํด์ ธ ์๋ค.
- ์ฃผ์ด์ง ์ข ์ด๋ฅผ ์ผ์ ํ ๊ท์น์ ๋ฐ๋ผ ์๋ผ์ ๋ค์ํ ํฌ๊ธฐ๋ฅผ ๊ฐ์ง ์ ์ฌ๊ฐํ ๋ชจ์์ ํ์์ ๋๋ ํ๋์ ์์ข ์ด๋ฅผ ๋ง๋ค๋ ค๊ณ ํ๋ค.
- ์ ์ฒด ์ข ์ด์ ํฌ๊ธฐ๊ฐ N×N(N=2k, k๋ 1 ์ด์ 7 ์ดํ์ ์์ฐ์) ์ด๋ผ๋ฉด ์ข ์ด๋ฅผ ์๋ฅด๋ ๊ท์น์ ๋ค์๊ณผ ๊ฐ๋ค.
- ์์ ๊ฐ์ ๊ท์น์ ๋ฐ๋ผ ์๋์ ๋ <๊ทธ๋ฆผ 3>์ <๊ทธ๋ฆผ 1>์ ์ข ์ด๋ฅผ ์ฒ์ ๋๋ ํ์ ์ํ๋ฅผ, <๊ทธ๋ฆผ 4>๋ ๋ ๋ฒ์งธ ๋๋ ํ์ ์ํ๋ฅผ, <๊ทธ๋ฆผ 5>๋ ์ต์ข ์ ์ผ๋ก ๋ง๋ค์ด์ง ๋ค์ํ ํฌ๊ธฐ์ 9์ฅ์ ํ์์ ์์ข ์ด์ 7์ฅ์ ํ๋์ ์์ข ์ด๋ฅผ ๋ณด์ฌ์ฃผ๊ณ ์๋ค.
- ์ ์ฒด ์ข ์ด๊ฐ ๋ชจ๋ ๊ฐ์ ์์ผ๋ก ์น ํด์ ธ ์์ง ์์ผ๋ฉด ๊ฐ๋ก์ ์ธ๋ก๋ก ์ค๊ฐ ๋ถ๋ถ์ ์๋ผ์ <๊ทธ๋ฆผ 2>์ I, II, III, IV์ ๊ฐ์ด ๋๊ฐ์ ํฌ๊ธฐ์ ๋ค ๊ฐ์ N/2 × N/2์์ข ์ด๋ก ๋๋๋ค.
- ๋๋์ด์ง ์ข ์ด I, II, III, IV ๊ฐ๊ฐ์ ๋ํด์๋ ์์์์ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ชจ๋ ๊ฐ์ ์์ผ๋ก ์น ํด์ ธ ์์ง ์์ผ๋ฉด ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ๋๊ฐ์ ํฌ๊ธฐ์ ๋ค ๊ฐ์ ์์ข ์ด๋ก ๋๋๋ค.
- ์ด์ ๊ฐ์ ๊ณผ์ ์ ์๋ผ์ง ์ข ์ด๊ฐ ๋ชจ๋ ํ์์ ๋๋ ๋ชจ๋ ํ๋์์ผ๋ก ์น ํด์ ธ ์๊ฑฐ๋, ํ๋์ ์ ์ฌ๊ฐํ ์นธ์ด ๋์ด ๋ ์ด์ ์๋ฅผ ์ ์์ ๋๊น์ง ๋ฐ๋ณตํ๋ค.
- ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ์ข ์ด์ ํ ๋ณ์ ๊ธธ์ด N๊ณผ ๊ฐ ์ ์ฌ๊ฐํ์นธ์ ์(ํ์์ ๋๋ ํ๋์)์ด ์ฃผ์ด์ง ๋ ์๋ผ์ง ํ์์ ์์ข ์ด์ ํ๋์ ์์ข ์ด์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒซ์งธ ์ค์๋ ์ ์ฒด ์ข ์ด์ ํ ๋ณ์ ๊ธธ์ด N์ด ์ฃผ์ด์ ธ ์๋ค. N์ 2, 4, 8, 16, 32, 64, 128 ์ค ํ๋์ด๋ค.
- ์์ข ์ด์ ๊ฐ ๊ฐ๋ก์ค์ ์ ์ฌ๊ฐํ์นธ๋ค์ ์์ด ์์ค๋ถํฐ ์ฐจ๋ก๋ก ๋์งธ ์ค๋ถํฐ ๋ง์ง๋ง ์ค๊น์ง ์ฃผ์ด์ง๋ค.
- ํ์์์ผ๋ก ์น ํด์ง ์นธ์ 0, ํ๋์์ผ๋ก ์น ํด์ง ์นธ์ 1๋ก ์ฃผ์ด์ง๋ฉฐ, ๊ฐ ์ซ์ ์ฌ์ด์๋ ๋น์นธ์ด ํ๋์ฉ ์๋ค.
- ์ฒซ์งธ ์ค์๋ ์๋ผ์ง ํ์์ ์์ข ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๊ณ , ๋์งธ ์ค์๋ ํ๋์ ์์ข ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ์ด๊ณผ ํ์ ์์์ ๋ถํฐ ๋์ ๊น์ง ์ฌ์ด์ฆ๋งํผ ๋์์ ๋, ์์์ ๊ณผ ํด๋น ์ง์ ์ ๊ฐ์ด ๊ฐ์ง ์๋ค๋ฉด ํด๋น ์์น์ ํด๋น ์ฌ์ด์ฆ ์ ์ฌ๊ฐํ์ผ๋ก ์์ข ์ด๋ฅผ ๋ง๋ค ์ ์๋ค๋ ๋ป์ด๋ค.
- ๋ฐ๋ผ์ ์ด์ ์์์ ๊ณผ ํ์ ์์์ ์ ํจ์ ๊ธฐ์ค์ผ๋ก 1์ฌ๋ถ๋ฉด, 2์ฌ๋ถ๋ฉด, 3์ฌ๋ถ๋ฉด, 4์ฌ๋ถ๋ฉด ์์์ ๊ธฐ์ค์ผ๋ก ๋๋๊ณ ์๋ ์ฌ์ด์ฆ๋ฅผ 2๋ถ์ 1๋ธ ํฌ๊ธฐ๋ฅผ ๋ฐํ์ผ๋ก DFS๋ฅผ ๋๋ฆฐ๋ค.
- ๋ง์ฝ ํด๋น ํฌ๊ธฐ๋ก ์์ข ์ด๋ฅผ ๋ง๋ค ์ ์๋ค๋ฉด ์ฒซ ์์ ์ง์ ์ ๊ฐ์ ํ๋จํด์ ํ๋์์ธ์ง ํฐ์์ธ์ง ๊ตฌ๋ถํ์ฌ ์นด์ดํธ ํ๊ณ returnํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ํธ๋๋ฐ ์๊พธ stackoverflow๊ฐ ๋์ ๋ญ๊ฐ ๋ฌธ์ ์ง ๊ณ์ ๊ณ ๋ฏผํ๋ ๊ฒ ๊ฐ๋ค.
- DFS๋ฅผ ๋๋ฆด ๋ ๊ธฐ์ ์กฐ๊ฑด์ ๋ช ํํ ์ค์ ํด์ฃผ์ง ์์ ๋ฌดํ DFS ํ์์ด ๋ฐ์ํ์ฌ stackoverflow๊ฐ ๋ฌ๋ ๊ฒ์ด์๋ค.
- ์์ผ๋ก ๊ธฐ์ ์กฐ๊ฑด์ ์ข ๋ ๊ผผ๊ผผํ ์ค์ ํ์ฌ์ผ๊ฒ ๋ค...
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ2630 {
static int N;
static int paper[][];
static int b_cnt;
static int w_cnt;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// ํ ๋ณ์ ๊ธธ์ด
N = Integer.parseInt(br.readLine());
// ์์ข
์ด๊ฐ ์น ํด์ง ๋ชจ์
paper = new int[N][N];
// ํ๋์ ์ข
์ด ์นด์ดํธ
b_cnt = 0;
// ํ์์ ์ข
์ด ์นด์ดํธ
w_cnt = 0;
for(int i = 0; i < N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++){
int n = Integer.parseInt(st.nextToken());
// ์ข
์ด์ ๊ฐ์ ์ ์ฅํ๋ ๋ฐฐ์ด ์ ์ข
์ด์ ์ ์ฅ
paper[i][j] = n;
}
}
DFS(0, 0, N);
System.out.println(w_cnt);
System.out.println(b_cnt);
}
static public void DFS(int l, int k, int S){
// ์ ์ฌ๊ฐํ์ผ๋ก ์๋ฅผ ์ ์๋์ง ์ฌ๋ถ ํ๋จ ๋ณ์
boolean TF = true;
for(int i = l; i < l + S; i++){
for(int j = k; j < k + S; j++){
// ๋ง์ฝ ์ข
์ด์ ์์๋ถ๋ถ๊ณผ ํด๋น ๋ถ๋ถ์ ๊ฐ์ด ๊ฐ์ง ์๋ค๋ฉด
if(paper[i][j] != paper[l][k]){
// ํด๋น ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ์ ํฐ์, ํ๋์์ผ๋ก ๋๋์ง ์๋๋ค๋
// ๋ป์ด๋ฏ๋ก false๋ก ๋ฐ๊พธ๊ณ ๋ฐ๋ณต๋ฌธ ์ข
๋ฃ
TF = false;
break;
}
}
if(!TF){
break;
}
}
// ๋ง์ฝ ํด๋น ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ์ ํ ์๊น๋ก ์น ํ ์ ์๋ค๋ฉด
// ํด๋น ์ ์ฌ๊ฐํ์ ์์๋ถ๋ถ์ ์ซ์๋ฅผ ํ์ธ ํ,
// ํฐ์์ด๋ ํ๋์ ์นด์ดํธ + 1
if(TF){
// ์ซ์๊ฐ 1์ด๋ผ๋ฉด ํ๋์ + 1
if(paper[l][k] == 1){
b_cnt = b_cnt + 1;
}
// ์ซ์๊ฐ 0์ด๋ผ๋ฉด ํฐ์ + 1
else if(paper[l][k] == 0){
w_cnt = w_cnt + 1;
}
}
// ํด๋น ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ์ผ๋ก ์๋ฅผ ์ ์๋ค๋ฉด 2๋ถ์ 1๊ธธ์ด๋ก ์๋ผ์
// ๋ค์ DFS๋ฅผ ๋๋ฆผ
else if(!TF){
int newS = S / 2;
// 2์ฌ๋ถ๋ฉด
DFS(l, k, newS);
// 1์ฌ๋ถ๋ฉด
DFS(l, k + newS, newS);
// 3์ฌ๋ถ๋ฉด
DFS(l + newS, k, newS);
// 4์ฌ๋ถ๋ฉด
DFS(l + newS, k + newS, newS);
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 2805 ๋๋ฌด ์๋ฅด๊ธฐ (2) | 2024.08.12 |
---|---|
[Java] BOJ 11279 ์ต๋ ํ (0) | 2024.08.11 |
[Java] BOJ 1541 ์์ด๋ฒ๋ฆฐ ๊ดํธ (0) | 2024.08.02 |
[Java] BOJ 1927 ์ต์ ํ (0) | 2024.08.01 |
[Java] BOJ 1260 DFS์ BFS (0) | 2024.08.01 |