[백준]2567번 색종이-2 - Java

문제

https://www.acmicpc.net/problem/2567

2567번: 색종이 - 2

 

풀이

몇번 풀어봤던 유형의 색종이 문제라 처음 읽었을 때는 한 5분이면 풀 수 있을 줄 알았다. 이전의 색종이 문제들은 내 블로그에도 두세문제 있으니까 찾아보면 될 듯????

 

근데 얘는 걔네들보다는 쪼오오오오끔 더 생각을 해야된다. 넓이를 구하는게 아니라 둘레를 구하는 것이기 때문.

우선 색종이를 붙인 칸이면 1로 싹 바꿔주고, 바꾼 후에 배열 한 칸마다 탐색을 한다. 탐색을 하면서 1인 칸은 사방탐색을 실시하는데 이때 0인 인접한 칸이 있으면 답인 count를 1씩 증가시켜주는 식으로 했다. 그렇게 하기 위해서

if (nr >= 1 && nr <= 100 && nc >= 1 && nc <= 100 && map[nr][nc] == 0) {
	count++;
}

사방 탐색하는 반복문 안에 이런 식으로 코드를 짰는데 이렇게 하면 배열을 딱맞게 map[100][100]으로 만들었을 경우에는 정답이 아니게 된다.

색종이가 map의 범위에 딱 맞게 붙은 경우라면 배열의 밖으로 나간 경우는 count하지 않기 때문이다!

 

그래서 나는 배열을 전체 도화지의 크기 100x100에서 상하좌우 1칸씩 더 해서 map[102][102] 배열을 만들어서 코드를 돌렸다

그랬더니 정답!

 

코드

// 2567번 색종이-2
// https://www.acmicpc.net/problem/2567

package BAEKJOON;

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

public class Num2567_색종이_2 {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[102][102];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            for (int j = a + 1; j <= a + 10; j++) {
                for (int k = b + 1; k <= b + 10; k++) {
                    map[j][k] = 1;
                }
            }
        }

        int count = 0;

        for (int i = 1; i <= 100; i++) {
            for (int j = 1; j <= 100; j++) {
                int r = i;
                int c = j;

                if (map[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        int nr = r + dr[k];
                        int nc = c + dc[k];

//                        if (nr >= 1 && nr <= 100 && nc >= 1 && nc <= 100 && map[nr][nc] == 0) {
//                            count++;
//                        }
                        if (map[nr][nc] == 0) {
                            count++;
                        }
                    }
                }
            }
        }

        System.out.println(count);
    }
}