[JAVA]백준 1355 - 구멍난 케이크 자르기

1355번: 구멍난 케이크 자르기 (acmicpc.net)

1355번: 구멍난 케이크 자르기

package baekjoon;

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

public class b1355 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int lc = Integer.parseInt(st.nextToken());
		int lh = Integer.parseInt(st.nextToken());
		int cake[][] = new int[lc*4][lc*4];
		
		for(int i = 0 ; i < lc*4 ; i++)
			Arrays.fill(cake[i], 1);
		
		int h = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < h ; i++) {
			int tmp = -Integer.parseInt(st.nextToken())*2+lc*2;
			for(int j = 0 ; j < lc*4 ; j++) {
				cake[tmp-1][j] = 0;
			}
		}
		
		int v = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < v; i++) {
			int tmp = -Integer.parseInt(st.nextToken())*2+lc*2;
			for(int j = 0 ; j < lc*4 ;j++) {
				cake[j][tmp-1] = 0;
			}
		}
		
		int tmp1 = lc - lh;
		int tmp2 = lc + lh;
		for(int i = tmp1*2 ; i < tmp2*2 ;i++) {
			for(int j = tmp1*2 ; j < tmp2*2 ;j++) {
				cake[i][j] = 0;
			}
		}
		
		int ans = 0;
		for(int i = 0 ; i < lc*4 ; i++) {
			for(int j = 0 ; j < lc*4; j++) {
				if(cake[i][j]==1) {
					ans++;
					dfs(i,j,cake,lc);
				}
			}
		}
		
		bw.write(ans+"");
		bw.close();
	}
	public static void dfs(int row, int col, int[][] a, int lc) {
		int dirX[] = {-1,-1,-1,1,1,1,0,0};
		int dirY[] = {-1,1,0,1,-1,0,-1,1};
		
		for(int i = 0 ; i < 8 ; i++) {
			int nx = col + dirX[i];
			int ny = row + dirY[i];
			if(nx >= 0 && nx < lc*4 && ny >= 0 && ny < lc*4) {
				if(a[ny][nx] == 1) {
					a[ny][nx] = 0;
					dfs(ny, nx, a, lc);
				}
			}
		}
	}
}

원래 절반이라 2 곱해야했잖아요

거기에 2를 더 곱해서 0과 1 사이에 공간을 하나 더 만들어서 선을 표현해주는 느낌이고

나머지는 기존 dfs 문제랑 동일합니다

백준 1355 구멍난 케이크 자르기 c++ (velog.io)

이 선생님 글 참고했는데 공간 하나 더 만드는 아이디어 완전 대박이었습니다 짱!~!

지금

개강하고 싶으면서도

개강하기싫은...고런...느낌이에요...