문제
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오.
예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다.
<그림 1>
입력
첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.
출력
첫째 줄에 색종이가 붙은 검은 영역의 둘레의 길이를 출력한다.
처음에는.. 예전에 수학 공식에서 구하듯이 큰 사각형 하나의 둘레를 구하려고 했다. 하지만 이 경우는 사진에서 가운데에 흰 사각형이 비어있는 경우를 체크하지 못한다. 결국 색종이 1처럼 2차원 배열에 값을 저장하여 풀었다.
1인 원소가 모서리에 있는지는, 주변의 원소를 보면 알 수 있다. 그래서 사방탐색을 활용하였다.
사방탐색을 하여 위아래, 양옆이 모두 1이면 모서리가 아니다.
또한 0이 한 개 있으면 모서리 하나만 둘레에 해당하고, 2개면 모서리 두개, 3개면 모서리 세 개에 해당한다.
그래서 0의 개수만큼 둘레에 더해주었다.
package BOJ0810;
import java.util.Scanner;
public class BOJ_2567_색종이2 {
static int[][] arr = new int[100][100];
static int[] dr = { 1, -1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int col = sc.nextInt();
int row = sc.nextInt();
for (int r = row; r < row + 10; r++) {
for (int c = col; c < col + 10; c++) {
if (arr[r][c] == 0)
arr[r][c] = 1;
}
}
}
int sum = 0;
for (int r = 0; r < 100; r++)
for (int c = 0; c < 100; c++) {
if (arr[r][c] == 1)
sum += isEdge(r, c);
}
System.out.println(sum);
}
static int isEdge(int r, int c) {
int cnt = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= 100 || nc < 0 || nc >= 100 || arr[nr][nc] == 0) {
cnt++;
}
}
return cnt;
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] N과 M (자바/Java) 순열, 조합, 중복순열, 중복조합 (0) | 2022.08.12 |
---|---|
[백준] 2527 - 직사각형 (자바/Java) (0) | 2022.08.11 |
[백준] 2407 - 조합 (자바/Java) BigInteger 클래스 (0) | 2022.08.09 |
[백준] 2564 - 경비원 (자바/Java) (0) | 2022.08.09 |
[백준] 1244 - 스위치 켜고 끄기 (자바/Java) (0) | 2022.08.09 |