백준 특정 알고리즘 문제 풀이 후, 체득하기 위해 정리하는 글입니다.
| 문제번호 | 제목 | 난이도 |
|---|---|---|
| 2630 | 색종이 만들기 | 실버 2 |
| 1992 | 쿼드트리 | 실버 1 |
| 1780 | 종이의 개수 | 실버 2 |
2630번 색종이 만들기
해결 코드:
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
* - 고민과 풀이:
*
* 재귀
* 1. 함수 형태 confetti(field, x,y, size)
* 2. base Condition 특정 조건에 해당하는 경우 해당 좌표에 해당하는 배열의 값 증가시키고 종료
* -> 모든 주어진 크기만큼 배열의 모든 좌표를 돌아 같은값으로만 이루어져있는지 확인
* 3. 재귀식
* 분할정복으로 4번 돌아주면 된다
* confetti(field, x,y, size/2);
* confetti(field, x,y+size/2, size/2);
* confetti(field, x+size/2,y, size/2);
* confetti(field, x+size/2,y+size/2, size/2);
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
public class Main {
static int[] ans = {0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] field = new int[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
field[i][j] = Integer.parseInt(st.nextToken());
}
}
confetti(field, 0,0, n);
for (int an : ans) {
bw.write(an+"\n");
}
br.close();
bw.close();
}
private static void confetti(int[][] field, int x, int y, int size) {
if(sameColor(field, x,y, size)){
ans[field[y][x]]++;
return;
}
int newSize = size / 2;
confetti(field, x,y, newSize);
confetti(field, x,y+ newSize, newSize);
confetti(field, x+ newSize,y, newSize);
confetti(field, x+ newSize,y + newSize, newSize);
}
private static boolean sameColor(int[][] field, int x, int y, int size) {
int now = field[y][x];
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
if(field[i][j] != now){
return false;
}
}
}
return true;
}
}
학습 정리:
- 일반적인 재귀 방식에 분할정복이 포함된 문제이다
- 이 문제와 같이 모든 좌표를 한번에 다 돌면서 찾을수도 있지만, 이렇게 쪼개서 4등분으로 각각을 탐색한다면 메모리를 더 효율적으로 사용할 수 있다
- 그래프에서 쪼개는 문제는 일반적으로 시작 지점의 x,y좌표를 기준으로 크기를 등분해서 1,2,3,4분면을 탐색하고 다시 쪼개는 방식으로 진행된다는 것을 기억하자
- base Condition도 특이한데, 일반적인 재귀의 종료 조건인 depth깊이가 일정치에 다다르거나 어떤 수보다 크거나 작을때랑 다르게 주어진 좌표크기내에서 모든 위치의 숫자가 같을 경우가 종료 조건이 된다.
- 분할정복의 base Condition은 일반 적인 방식과 차이가 있다는 것을 꼭 기억하자
1992번 쿼드트리
해결 코드:
import java.io.*;
import java.util.*;
/**
* 고민과 풀이:
*
* 재귀
* 1. 함수식 quadTree(field, size, x,y)
* 2. base Condition 특정 조건을 만족하는 경우
* -> 주어진 범위 내에서 배열을 순회했을 때, 모두 같은 경우
* 3. 재귀식 4개로 분할정복해서 푼다 -> 참고로 아래 순서 지켜야 함...
* - quadTree(field, size/2, x,y)
* - quadTree(field, size/2, x+size/2,y)
* - quadTree(field, size/2, x,y+size/2)
* - quadTree(field, size/2, x+size/2,y+size/2)
* - 또한 추가로 각 분할정복을 통과하기전에 "("을 추가한다.
* - 마지막 분할 정복을 통과하면 ")"울 추가한다.
*
* 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*
*/
public class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] field = new int[n][n];
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split("");
for (int j = 0; j < n; j++) {
field[i][j] = Integer.parseInt(input[j]);
}
}
quadTree(field, n, 0,0);
bw.write(sb.toString());
br.close();
bw.close();
}
private static void quadTree(int[][] field, int size, int x, int y) {
if(isSame(field, size, x,y)){
sb.append(field[y][x]);
return;
}
int newSize = size / 2;
sb.append("(");
quadTree(field, newSize, x,y);
quadTree(field, newSize, x+newSize,y);
quadTree(field, newSize, x,y+newSize);
quadTree(field, newSize, x+newSize,y+newSize);
sb.append(")");
}
private static boolean isSame(int[][] field, int size, int x, int y) {
int now = field[y][x];
for (int i = y; i < y+size; i++) {
for (int j = x; j < x + size; j++) {
if(now != field[i][j]){
return false;
}
}
}
return true;
}
}학습 정리:
- 색종이 만들기와 비슷한 유형의 문제라 푸는데 큰 어려움은 없었따.
- 한가지 추가된다면 각 분할정복 재귀식이 실행되기 전과 실행된 후에 (와 )가 추가되다는 점이다.
1780번 종이의 개수
해결 코드:
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
* - 고민과 풀이:
* 재귀
* 1. 함수 형태: paper(종이 정보가 담긴 배열, x,y, n/3)
* 2. base Condition 특정 함수 조건을 만족시키는 경우 -> 그 줄의 좌표를 가져와서 해당 Map의 값을 증가시켜준다
* -> 이떄 특정 함수 조건은 조어진 필드 범위 내에서 같은 숫자로만 이루어져 있는지 확인하는 함수이다.
* 3. 재귀식 총 9개를 돌려준다.
* paper(종이 정보가 담긴 배열, x,y, n/3)
* paper(종이 정보가 담긴 배열, x+n/3,y, n/3)
* paper(종이 정보가 담긴 배열, x+2*(n/3),y, n/3)
* paper(종이 정보가 담긴 배열, x,y+n/3, n/3)
* paper(종이 정보가 담긴 배열, x+n/3,y+n/3, n/3)
* paper(종이 정보가 담긴 배열, x+2*(n/3),y+n/3, n/3)
* paper(종이 정보가 담긴 배열, x,y+2*(n/3), n/3)
* paper(종이 정보가 담긴 배열, x+n/3,y+2*(n/3), n/3)
* paper(종이 정보가 담긴 배열, x+2*(n/3),y+2*(n/3), n/3)
*
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
public class Main {
static Map<Integer, Integer> map = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] field = new int[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
field[i][j] = Integer.parseInt(st.nextToken());
}
}
map.put(-1,0);
map.put(0,0);
map.put(1,0);
paper(field, 0,0, n);
for (Integer i : map.values()){
bw.write(i+"\n");
}
br.close();
bw.close();
}
private static void paper(int[][] field, int x, int y, int size) {
if(onlyOne(field, x,y,size)){
map.put(field[y][x],map.get(field[y][x])+1);
return;
}
int newSize = size / 3;
paper(field,x,y, newSize);
paper(field,x+ newSize,y, newSize);
paper(field,x+(2* (newSize)),y, newSize);
paper(field,x,y + newSize, newSize);
paper(field,x+ newSize,y + newSize, newSize);
paper(field,x+(2* (newSize)),y + newSize, newSize);
paper(field,x,y+(2* (newSize)), newSize);
paper(field,x+ newSize,y+(2* (newSize)), newSize);
paper(field,x+(2* (newSize)),y+(2* (newSize)), newSize);
}
private static boolean onlyOne(int[][] field, int x, int y, int size) {
int now = field[y][x];
for (int i = y; i < y+size; i++) {
for (int j = x; j < x+size; j++) {
if(field[i][j] != now){
return false;
}
}
}
return true;
}
}
학습 정리:
- 기존 4개 분할 정복에서 9개로 늘어난 분할정복 문제였다. 큰 어려움은 없이 해결하였다.
- 한가지 추가한 것은 -1,0,1의 개수를 세어주어야 하므로, Map을 활용하여서 더 간단하게 해결하였다.
Software Developer