문제 링크 : https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.
www.acmicpc.net
종이의 개수 문제를 접했을 때 분할 하는 방법을 몰랐다.
그래서 아래의 색종이 만들기 문제를 먼저 풀면서 분할 정복의 핵심 로직을 익혔다.
두 문제를 다 풀어보니 둘중 뭐가 더 어렵다고 말하기 힘들정도로 비슷하다.
종이의 개수 문제가 분할의 범위가 커졌을뿐이다.
그래도 분할의 범위가 작은 색종이 만들기 부터 풀고나니 종이의 개수 문제를 대하는 태도가 달라졌다.
난이도 낮은 문제를 푼게 아주 큰 도움이 되었다.
[BOJ 분할정복] 색종이 만들기 2630.JAVA
문제 링크 : www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색..
nkt-docs.tistory.com
다음과 같이 소스를 공유합니다.
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.StringTokenizer;
public class 종이의 개수 {
public static int N;
public static int[][] map;
public static int[] res = new int[3];
public static void main(String[] arsg) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
divide(0, 0, N);
StringBuilder sb = new StringBuilder();
sb.append(res[2]).append("\n");
sb.append(res[0]).append("\n");
sb.append(res[1]).append("\n");
System.out.println(sb.toString());
}
public static void divide(int r, int c, int s) {
if(checkNum(r, c, s)) {
int num = map[r][c];
if(num == -1) {
res[2]++;
}else {
res[num]++;
}
return;
}
int ns = s/3;
divide(r, c, ns);
divide(r, c+ns, ns);
divide(r, c+ns*2, ns);
divide(r+ns, c, ns);
divide(r+ns*2, c, ns);
divide(r+ns, c+ns, ns);
divide(r+ns, c+ns*2, ns);
divide(r+ns*2, c+ns, ns);
divide(r+ns*2, c+ns*2, ns);
}
public static boolean checkNum(int r, int c, int s) {
int num = map[r][c];
for(int i = r; i < r+s; i++) {
for(int j = c; j < c+s; j++) {
if(map[i][j] != num) return false;
}
}
return true;
}
}핵심 로직은 divide를 재귀로 호출하는 부분이다.
divide의 파라미터를 r(row), c(col), s(size)로 받는다.
r = 0, c = 0, s = 9
예를 들면
1. 배열[0][0] ~ 배열[8][8] 까지 배열을 체크(checkNum)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.
2. s(size)를 3으로 나누어 분할 한다.
3. 배열[0][0] ~ 배열[2][2] 까지 배열을 체크(checkNum)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.
4. 배열[0][2] ~ 배열[2][4] 까지 배열을 체크(checkNum)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.
5. 배열[0][4] ~ 배열[2][6] 까지 배열을 체크(checkNum)하여 같은 종이인지 확인(if문) 후 해당 번호의 종이를 +1한다.
이런식으로 전체 배열의 시작 위치와 탐색해야 하는 크기를 이용하여 1칸의 종이까지 체크할 수 있다.
'알고리즘 > 문제풀이 - 백준온라인저지' 카테고리의 다른 글
| [BOJ 그리디] 도서관 1461.JAVA (0) | 2021.06.01 |
|---|---|
| [BOJ 분할정복] Moo 게임 5094.JAVA (0) | 2021.05.15 |
| [BOJ 분할정복] 색종이 만들기 2630.JAVA (0) | 2021.05.13 |
| [BOJ] 배열 돌리기 17276.JAVA (0) | 2021.04.14 |
| [BOJ] 빗물 14719.JAVA (0) | 2021.04.14 |