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

[문제]

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다.

[조건]

• 시간 제한 : 1초
• 메모리 제한 : 128MB

[입력]

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다. 

[출력]

첫째 줄에 색종이가 붙은 검은 영역의 둘레의 길이를 출력한다.

[문제 풀이]

• 색종이가 배열 끝에 존재하는 경우를 고려하여 배열 크기를 102*102로 만들어줌
• 배열 입력시 둘레는 2, 그 외는 1로 입력받음 → 아래 사진 참고
• 둘레일 때 사방탐색을 통해 주변에 있는 0의 개수만큼 더해 최종 둘레 구함
• 0이 한 개라면 → 일반 둘레
• 0이 두 개라면 → 꼭짓점

입력을 통해 만들어진 배열 모습

import java.io.*;
import java.util.*;

public class Main {
	static StringTokenizer st;
	static BufferedReader br;

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

		int N = Integer.parseInt(st.nextToken());

		int[][] paper = new int[102][102];
		int res = 0;

		// 배열
		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			int rs = Integer.parseInt(st.nextToken())+1;
			int cs = Integer.parseInt(st.nextToken())+1;
			for (int r = rs; r <= rs + 9; r++) {
				for (int c = cs; c <= cs + 9; c++) {
					if (r == rs || r == rs + 9 || c == cs || c == cs + 9) {
						paper[r][c] = 2;
					} else {
						paper[r][c] = 1;
					}
				}
			}
		}
		
		int[] dr = {-1, 1, 0, 0};
		int[] dc = {0, 0, -1, 1};

		for (int r = 0; r < 102; r++) {
			for (int c = 0; c < 102; c++) {
				if (paper[r][c] == 2) {
					int zero = 0;
					for (int d=0; d<4; d++) {
						int nr = r+dr[d];
						int nc = c+dc[d];
						if(paper[nr][nc]==0) {
							zero++;
						}
					}
					res+=zero;
				}
			}
		}
		System.out.println(res);
	}
}

 

[소감]

• 아이디어 구상에서 어려움을 겪음
• 아이디어 1 : 색종이 배열 속 행렬의 최대최소값을 구해 총 둘레길이 구하기 → 속 둘레 구할 수 없음
• 아이디어 2 : 색종이 1, 그외 0으로 입력받고 0의 개수 구해 둘레 조정 → 구멍의 위치를 찾기 위해 연산이 복잡해짐

 

출처 : 백준 https://www.acmicpc.net/problem/2567