[백준]2567번 색종이 - 2(JAVA)

0. 문제 링크

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

2567번: 색종이 - 2

 

1. 문제 설명

1) 가로, 세로의 크기가 100인 정사각형 모양 흰색 도화지

2) 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이 붙이기

3) 색종이가 붙은 검은 영역의 둘레의 길이 구하기

 

2. 입출력

// input
4
3 7
5 2
15 7
13 14

// output
96

 

3. 코드

import java.util.Scanner;

public class b2567 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] dr = {-1, 1, 0, 0}; // 사방탐색
		int[] dc = {0, 0, -1, 1};
		int ans = 0; // 정답(둘레)

		int N = sc.nextInt(); // 색종이의 수
		int[][] rc = new int[N][2]; // 색종이 붙일 위치 배열
		int max_rc = 0; // 색종이 최대 좌표
		for(int n = 0; n < N; n++) {
			rc[n][1] = sc.nextInt() + 1;
			rc[n][0] = sc.nextInt() + 1;
			max_rc = Math.max(max_rc, Math.max(rc[n][1], rc[n][0]));
		}
		max_rc += 11; // 10 만큼 붙이고도 여백 하나 추가
		int[][] map = new int[max_rc][max_rc]; // 흰색 도화지 축소해서 만들기
		
		for(int n = 0; n < N; n++) { // 색종이 붙이기
			int r = rc[n][0];
			int c = rc[n][1];
			for(int i = r; i < r+10; i++) {
				for(int j = c; j < c+10; j++) {
					map[i][j] = 1;
				}
			}
		}
	
		for(int i = 0; i < max_rc; i++) { 	// 사방탐색 후 주변이 0 값이 있으면 둘레로 계산
			for(int j = 0; j < max_rc; j++) {
				if(map[i][j] == 1) {
					for(int d = 0; d < 4; d++) {
						int nr = i + dr[d];
						int nc = j + dc[d];
						if(nr > 0 && nr <= max_rc && nc > 0 && nc <= max_rc && map[nr][nc] == 0) {
							ans++;
						}
					}
				}
			}
		}
		
		System.out.println(ans);
	}
}

 

실행 결과

 

4. 회고

1) 100*100 배열을 만들면 시간 초과/메모리 부족이 일어나므로 max_rc를 통해 도화지의 범위를 구함.

2) 둘레는 검은색 도화지를 기준으로 사방탐색을 통해 칠하지 않은 영역의 길이를 구함

3) 사방탐색 시 범위를 벗어나는 맨 끝의 경우에는 계산하기 어려우니 (0,0)->(1,1)로 옮겨서 구함. 마찬가지로 max_rc도 10이 아니라 11을 더해서 여백을 만듦

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b2567.java