[java][boj][s4] 2567. 색종이 - 2

2567번: 색종이 - 2

문제

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

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

<그림 1>

입력

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

출력

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

풀이

/*
 * 입력
 * 1. 색종이의 수 N
 * 2. 색종이를 붙일 위치 x y (왼쪽 아래 좌표, 크기는 10)
 * 출력
 * 색종이가 붙은 영역의 둘레
 * 
 * >> 1인 부분만 골라 사방 탐색 해서 한쪽이 0이 있으면 +1
 */

저번에 했던 넓이 구하는 공식에서 약간 더 어려워진 느낌이지만 생각보다 간단하다 아래 첨부한 링크가 색종이 넓이를 구하는 문제다

[java][boj][b1] 2563. 색종이

그때는 1인 부분을 전부 찾아서 더하면 끝이었지만 이번에는 모서리 부분만 구해야 하기 때문에 0(색종이를 붙이지 않은 부분)과 맞닿은 1(색종이를 붙인 부분)을 찾아야 한다 1인 부분을 골라 사방탐색을 하면서 0과 맞닿은 부분이 있다면 +1을 해 주면 된다

코드

package im형필수문제;

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

public class s4_2567_색종이2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		int[][] arr = new int[101][101];
		
		int N = Integer.parseInt(br.readLine());
		int len = 0;
		
		for(int n = 0; n < N; n++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			for(int i = x; i < 10+x; i++) { //x와 y 좌표로부터 10만큼 색종이 붙이기
				for(int j = y; j < 10+y; j++) {
					arr[i][j] = 1;
				}
			}
		} // 색종이 붙이기
		
		for(int i = 0; i < 101; i++) {
			for(int j = 0; j < 101; j++) {
				if(arr[i][j]==1) { // 색종이가 붙은 부분 탐색
					for(int k = 0; k < 4; k++) {
						int x = i+dx[k];
						int y = j+dy[k];
						if(arr[x][y]==0) len++; // 사방탐색 중 0인 부분이 있으면 둘레로 계산
					}
				}
			}
		} // 둘레 구하기
		
		System.out.println(len);
	}
}

결과

 

#자바 #java #boj #백준 #알고리즘