백준 2567번 : 색종이-2

문제

2567번: 색종이 - 2 (acmicpc.net)

2567번: 색종이 - 2

 

색종이를 겹쳐서 붙였을 때, 전체 색종이의 둘레를 구하는 문제

---

아이디어

두가지 방법으로 풀이할 수 있는데 두 방법 모두 '우선 색종이를 붙인 다음' 시작한다.
색종이를 붙이는 방법은 이중 for 문 돌면서 0을 1로 바꿔주면 된다.

방법 1. 이중 for문으로 풀이

• 흰 도화지 전체를 돌면서 진행
• 색종이 부분(= 값이 1인)을 만나면, 4개의 방향에 있는 값을 조사
  
• 4변을 조사하는 방법은 {{0, 1}, {0, -1}, {1, 0}, {-1, 0}} 이 저장된 direction 배열을 돌면서 해당하는 값을 더해주면 됨
• 어떤 변의 인덱스가 0보다 작거나 99보다 크면, 흰 도화지의 모서리에 해당하므로 둘레 ++
• 어떤 변의 값이 0이면 바로 검은 색종이의 모서리에 해당하므로 둘레 ++

방법 2. 재귀함수로 풀이

• 흰 도화지를 돌며 1이 발견되는 지점에서 시작해서 4개의 변을 재귀적으로 탐색
• 한번 조사한 좌표를 다시 조사하면, 그 좌표는 스스로를 또 조사하고, 또 조사하고... 하여 무한 루프 발생 => 😵
• 이를 방지하기 위해서 조사를 시작하자마자 값을 -1로 바꿔줌
• 이후 4개의 변을 조사하는데, 이때 1이면 방법 1에서 쓴 것과 동일한 로직으로 둘레++ 해줌
• 또한, 조사하는 과정 중에서 조사한 값이 1이면 재귀함수 호출해서 같은 동작 반복

내가 처음에 생각했던 '1과 0 구분하지 않고 모두 재귀함수 호출'하는 방법은 이중 for문과 다를게 없음
❗해당하는 값이 1임을 보장한다는게 이 알고리즘을 단순화하는 가장 큰 요인인듯❗

---

코드

방법 1. 이중 for문으로 풀이

package paperRound;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int paperNum = Integer.parseInt(br.readLine());
        int[][] white = new int[100][100];

        for (int i = 0; i < paperNum; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 색종이 붙이기
            for(int j=0; j<10; j++){
                for(int k=0; k<10; k++){
                    white[x+j][y+k] = 1;
                }
            }
        }

        // 둘레 구하기
//        int[] dx = {0,0,1,-1};
//        int[] dy = {1,-1,0,0};
        // 방향을 담은 배열을 위처럼 만들지 말고 아래처럼 만들면 가독성 높아짐
        int[][] d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int round = 0;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if(white[i][j]==1){
                    for(int k=0; k<d.length; k++){
                        int x = d[k][0];
                        int y = d[k][1];
                        if(i+x <0 || i+x > 99 || j+y<0 || j+y>99){
                            round++;
                        } else if(white[i+x][j+y]==0){
                            round++;
                        }
                    }
                }
            }
        }
        System.out.println(round);
    }
}

 

방법 2. 재귀함수로 풀이 

package paperRoundByrecursion;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int paperNum = Integer.parseInt(br.readLine());
        int[][] white = new int[100][100];

        for (int i = 0; i < paperNum; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 색종이 붙이기
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    white[x + j][y + k] = 1;
                }
            }
        }

        int[][] d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        int result = 0;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                // 해당 위치가 1일때만 실행됨
                if(white[i][j]==1){
                    result += recur(white, d,i,j);
                }
            }
        }

        System.out.println(result);
    }

    public static int recur(int[][] white, int[][]d, int x, int y) {
        white[x][y] = -1;

        // 해당하는 값이 1임을 보장한다는게 이 알고리즘을 단순화하는 가장 큰 요인인듯
        int cnt = 0;
        for (int i = 0; i < d.length; i++) {
            int dx = x + d[i][0];
            int dy = y + d[i][1];
            if (dx < 0 || dx > 99 || dy < 0 || dy > 99 || white[dx][dy] == 0) { // 1인데 영역이 벗어나거나 물과 만나면 더 나아가면 안됨
                cnt++;
            }else {
                if(white[dx][dy]==1){
                    cnt += recur(white, d, dx,dy);
                }
            }
        }
        return cnt;
    }
}

 

---

알게된 것

재귀함수로 푸는 방법을 내 힘으로 풀려다가 약 세시간동안 삽질...
결국 무엇이 잘못되었는지 알게 되었고 이번 경험을 통해 재귀함수의 활용에 대한 이해를 올릴 수 있게 되었음
재귀함수를 사용하는데에 항상 어려움을 겪는데, 많이 하다보면 내가 설계하는 것도 빨라지겠지.!! 다시 파이팅 하자.