[백준] (JAVA) 색종이 만들기
문제
https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
설명
입출력
나의 풀이
풀이 과정
재귀 유형에서 선택한 문제이기 때문에 종료 조건과 재귀 호출을 생각하는 것에 초점을 맞추고 흐름을 분석하지 않으려고 노력했다.
우선 재귀가 호출될 때마다 N의 크기가 1/2씩 줄어들고 줄어든 색종이의 모든 칸이 0이거나 1이면 종료된다고 생각했다.
종료 조건 : 모든 칸이 0이거나 모든 칸이 1일 때 종료
재귀 호출: 재귀 함수를 호출할 때마다 색종이의 크기가 규칙적으로 1/2이 된다.
위의 생각을 바탕으로 "아! 재귀 함수 안에 첫 칸(0,0) 위치가 0또는 1일 때로 나누어서 모든 칸을 검사하고
다른 색의 칸이면 색종이의 크기를 1/2로 잘라서 다시 재귀 함수에 넣어야겠다."라는 생각으로 밑의 코드를 작성했다.
import java.util.*;
import java.io.*;
public class BJ_2630 {
public static int[][] board;
public static int w;
public static int b;
public static void main(String[] args) throws IOException {
// 1. 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
board = new int[N][N];
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
// System.out.println(Arrays.deepToString(board));
// 2. 재귀함수 적기 (매개변수 생각하면서)
rec(board, N, N);
// 3. 출력 생각하면서 미리 적기
// 1: blue, 0: white
System.out.println(w);
System.out.println(b);
}
// 4. 매개변수 생각하면서 먼저 적고 안에 함수 구체화 하기
public static void rec (int[][] x, int row, int col) {
if (x[0][0] == 0) {
for(int i=0; i < x.length; i++) {
for(int j=0; j < x[i].length; j++) {
if (x[i][j] == 1) {
rec();
} else {
w++;
return;
}
}
}
} else {
for(int i=0; i < x.length; i++) {
for(int j=0; j < x[i].length; j++) {
if (x[i][j] == 0) {
rec();
} else {
b++;
return;
}
}
}
}
}
}결과는 실패!!
색종이를 2차원 배열 board에 선언했는데 2차원 배열을 잘라서 재귀 함수에 담는 코드를 구현하지 못했다..
다른 분들의 코드를 참고한 결과 접근 종료 조건과 재귀 호출 방식은 맞게 생각했지만
2차원 배열을 잘라서 함수에 넣는 게 아닌 검사할 2차원 배열의 위치를 넣어주면 배열을 자르지 않고도 자른 것처럼 구현될 수 있었다.
아래는 재귀 함수 rec와 모든 칸의 색을 검사하는 colorCheck 함수를 구현한 코드이다.
import java.util.*;
import java.io.*;
public class BJ_2630 {
public static int[][] board;
public static int w;
public static int b;
public static void main(String[] args) throws IOException {
// 1. 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
board = new int[N][N];
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
// 2. 재귀함수 적기 (매개변수 생각하면서)
rec(0, 0, N);
// 3. 출력 생각하면서 미리 적기
// 1: blue, 0: white
System.out.println(w);
System.out.println(b);
}
// 4. 매개변수 생각하면서 먼저 적고 안에 함수 구체화 하기
public static void rec (int x, int y, int size) {
if(colorCheck(x,y,size)) {
if(board[x][y] == 1) b++;
else w++;
} else {
size = size / 2;
rec(x, y, size);
rec(x, y + size, size);
rec(x + size, y, size);
rec(x + size, y + size, size);
}
}
public static boolean colorCheck(int x, int y, int size) {
if (size == 1) {
return true;
} else {
for(int i=x; i < x + size; i++) {
for(int j = y; j < y + size; j++) {
if(board[i][j] != board[x][y]){
return false;
}
}
}
return true;
}
}
}결과는 성공!
size = size / 2;
rec(x, y, size);
rec(x, y + size, size);
rec(x + size, y, size);
rec(x + size, y + size, size);
위의 재귀 호출 부분을 자세히 분석해보자.
재귀 함수의 매개변수 구성 : rec(행의 시작점, 열의 시작점, N/2로 줄어든 크기)
첫 재귀 호출 rec(0,0,8)후에 4번의 재귀 함수에 각각 배열의 시작점을 바꿔서 넣어준다.
각각 rec(0,0,4) rec(0,4,4) rec(4,0,4) rec(4,4,4) 로 재귀 함수가 호출된다.
이런 식으로 재귀 함수가 반복이 된다!
하지만 재귀 함수 안에서 colorCheck과정까지 한 번에 구현해보고 싶어서 colorCheck함수를 없애고 재귀 함수 안에서
모든 과정이 진행되도록 바꿔보았다.
import java.util.*;
import java.io.*;
// 재귀함수 하나로 합침
public class Main {
public static int[][] board;
public static int w;
public static int b;
public static boolean color = true;
public static void main(String[] args) throws IOException {
// 1. 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
board = new int[N][N];
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
// 2. 재귀함수 적기 (매개변수 생각하면서)
rec(0, 0, N);
// 3. 출력 생각하면서 미리 적기
// 1: blue, 0: white
System.out.println(w);
System.out.println(b);
}
// 4. 매개변수 생각하면서 먼저 적고 안에 함수 구체화 하기
public static void rec (int x, int y, int size) {
// 같은 색 확인
for (int i = x; i < x + size; i++) {
for (int j = y; j < y + size; j++) {
if (board[i][j] != board[x][y]) {
color = false;
}
}
}
if (color && board[x][y] == 1) {
b++;
} else if (color && board[x][y] == 0) {
w++;
} else if (!color) {
color = true;
size = size / 2;
rec(x, y, size);
rec(x, y + size, size);
rec(x + size, y, size);
rec(x + size, y + size, size);
}
}
}거의 비슷한 것 같긴한데.... 그래도 합쳐보았다!
번외로 처음에 아래 코드처럼 합쳤을 때 결과가 틀렸는데 중간에 재귀 호출이 끝나면서 b나 w가 불필요하게 더해졌었다.
public static void rec (int x, int y, int size) {
// 같은 색 확인
for (int i = x; i < x + size; i++) {
for (int j = y; j < y + size; j++) {
if (board[i][j] != board[x][y]) {
size = size / 2;
rec(x, y, size);
rec(x, y + size, size);
rec(x + size, y, size);
rec(x + size, y + size, size);
}
}
}
if (color && board[x][y] == 1) {
System.out.println("b 더해짐");
b++;
} else {
System.out.println("w 더해짐");
w++;
}
}