/ BOJ

BOJ_2567_색종이2_JAVA

문제 : 색종이2

링크 : BOJ_2567_색종이2

접근 방식

이전에 풀었던 색종이 문제의 확장형이다. 100*100크기에 색종이를 겹치는 건 같지만, 넓이를 구했던 그 때와 달리 이번에는 둘레를 구해야 한다. 넓이를 구할 때는 배열 내부의 값을 모두 카운트하면 해결되는 문제였다.

둘레를 구하는 법은 막상 떠올릴려고 하면 어려웠다. 하지만 배열을 한 번 출력해보니 실마리가 보였다.

핵심은 1과 인접한 0의 개수였다. 색종이의 크기는 10*10이고 정사각형이다. 색종이를 모두 1로 채워넣는다고 할 때 색종이의 모서리는 항상 0과 맞닿아있다. 꼭짓점 부분은 2개의 0과 인접하고, 그 부분은 길이를 2로 칠 수 있다. 이를 토대로 유추했을 때, 색종이의 둘레는 배열을 탐색하여 값이 1인 노드와 인접해있는 0의 개수일 것이다. 다만, 배열을 100, 100으로 설정할 경우, 0만 체크하면 안되고 배열의 경계값도 주의해야 한다.

풀이 방법

  1. 100*100 크기의 int 타입 2차원 배열을 생성한다.

  2. 색종이의 좌표를 읽어들여 각 좌표별로 10*10만큼 1을 입력한다.

  3. 배열 전체를 탐색하며 1과 인접한 0의 개수를 센다. 1과 인접한 곳이 배열의 경계일 경우에도 카운트를 더해준다.

  4. 탐색이 종료된 후 카운트한 값을 출력한다.

소스 코드


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

public class BOJ_2567_색종이2 {
	static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());
		StringTokenizer st;


		// 100*100 크기 배열 생성
		int[][] arr = new int[100][100];

		// 주어진 좌표로부터 10*10만큼 1 집어넣기
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(in.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			for(int j = a; j <a+10;j++) {
				for(int k = b;k<b+10;k++) {
					arr[j][k] = 1;
				}
			}
		}
		// 둘레를 저장할 변수
		int cnt = 0;

		// 배열 전체 탐색 하며 1 주변의 0의 개수를 세기, 1 주변이 배열의 경계일 경우도 cnt를 더해준다
		for(int i=0;i<100;i++) {
			for(int j=0;j<100;j++) {
				// 배열에서 1을 만나면
				if(arr[i][j] == 1) {
					// 4방탐색
					for(int d = 0; d < 4; d++) {
						int dx = i + dir[d][0];
						int dy = j + dir[d][1];
						// 배열의 경계를 체크하여, 1 주변이 배열의 경계라면 cnt를 1 더해준다.
						if(dx < 0 || dx >= 100 || dy < 0 || dy >= 100) {
							cnt++;
						}
						// 배열의 경계 안에 있을 때, 1 주변에 0이 있다면 cnt를 1 더해준다.
						if(dx >= 0 && dx < 100 && dy >= 0 && dy < 100 && arr[dx][dy] == 0) {
							cnt++;
						}
					}
				}
			}
		}

		System.out.println(cnt);
	}

}