[백준 실버 4] 2567번: 색종이 - 2

문제

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

2567번: 색종이 - 2

 

 

풀이

• 가로, 세로 길이가 100인 도화지 위에 길이가 10인 정사각형 색종이를 도화지와 평행하게 붙인다.
• 이러한 방식으로 색종이를 여러장 붙였을 때, 둘레의 길이를 구한다.
• 중간에 구멍이 뚫린 모양도 둘레에 포함한다.

 

수학적인 방법으로 접근하려고 했지만 중간에 둘레가 생기는 경우를 계산하기 위해서 그리디한 방법으로 접근하였다. 도화지를 크기가 100 X 100인 2차원 배열로 생각한다. 이때 배열의 하나의 원소는 1 X 1 크기의 정사각형이 된다. 모든 배열의 위치에서 상하좌우를 탐색하여 색종이가 없는 빈 공간으로 판별되는 경우가 바로 가장자리가 된다.

 

먼저 색종이가 존재하는 부분을 모두 표시하여 준다. boolean 배열로 선언하여 true로 만들어 주었다.

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

    for (int i = x; i < x + 10; i++) {
        for (int j = y; j < y + 10; j++) {
            paper[i][j] = true;
        }
    }
}

 

그리고 도화지 위를 모두 탐색하며 각 사각형의 위치에서 사방을 탐색한다. 이때, 탐색하는 위치는 색종이가 존재하는 도화지, 즉 2차원 배열이 true인 곳에서 시작한다.

사방 탐색을 하기 위해서는 방향을 표시하는 배열이 추가로 필요하다. 현재 배열을 기준으로 한 칸씩 이동하며 탐색한다.

static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { 1, 0, -1, 0 };

...

if (paper[i][j]) {
    for (int d = 0; d < 4; d++) {
        int nx = i + dx[d];
        int ny = j + dy[d];

		...
    }
}

 

 

이때, 가장자리로 판별하는 기준은 paper[nx][ny]가 false가 되는 경우이다. 또, 색종이가 도화지의 가장자리에 맞닿은 경우, 사방 탐색이 배열의 영역 바깥으로 나갔기 때문에 추가적으로 조건이 필요하다.

if (!paper[nx][ny] || nx < 0 || nx > 100 || ny < 0 || ny > 100)
    border++;

 

 

한 방향이 가장자리라고 판별났더라도 다른 방향이 가장자리가 아니라는 법은 없다. 꼭지점에 해당하는 부분일 수도 있기 때문이다. 그렇기 때문에 모든 방향을 빠짐없이 체크해야 한다.

 

 

전체 코드 (Java)

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

public class Main {
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		boolean[][] paper = new boolean[101][101];
		int border = 0;

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

			for (int i = x; i < x + 10; i++) {
				for (int j = y; j < y + 10; j++) {
					paper[i][j] = true;
				}
			}
		}

		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				if (paper[i][j]) {
					for (int d = 0; d < 4; d++) {
						int nx = i + dx[d];
						int ny = j + dy[d];

						if (!paper[nx][ny] || nx < 0 || nx > 100 || ny < 0 || ny > 100)
							border++;
					}
				}

			}
		}

		System.out.println(border);

	}

}

 

 

후기

그리디하게 생각하지 않고 수학적으로 접근하여 답을 찾아내려고 하다가 시간을 생각보다 많이 썼다. 입력값의 범위를 보고 좀 더 유연하게 생각할 수 있도록 해야겠다.