백준 18808 - 스티커 붙이기(Java)

1. 유형

구현

 

2. 자료구조

- 3차원 배열(스티커 저장)

 

3. 기능

- 90도 돌리기

- 노트북에 붙이기

- 붙일 수 있는 위치 찾기

 

4. 풀이

90도를 돌릴때 생각할 점은 스티커가 직사각형 이라는 점이다.

때문에 일반적으로 90도를 돌리는게 아니라 배열의 크기를 가로 세로를 바꾼다음 다시 설정해야 한다.

그 후, 90도 돌리기

 

노트북에 붙이는 것은 노트북을 2중 탐색하면서 하나씩 비교해준다.

노트북이 비어있고 스티커가 1이라면 붙 일 수 있다.

스키티커를 전부 다 붙일 수 있다면, flag값을 사용해서 다음 스티커로 넘어간다.

 

마지막에 노트북을 2중 탐새해서 1의 갯수를 세어준다.

 

코드.

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

public class Main {
	static int N, M, K, map[][], R, C, arr[][][];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		K = Integer.valueOf(st.nextToken());
		map = new int[N][M];
		arr = new int[K][][];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(in.readLine());
			R = Integer.valueOf(st.nextToken());
			C = Integer.valueOf(st.nextToken());
			arr[i] = new int[R][C];
			for (int r = 0; r < R; r++) {
				st = new StringTokenizer(in.readLine());
				for (int c = 0; c < C; c++) {
					arr[i][r][c] = Integer.valueOf(st.nextToken());
				}
			}
		}
		for (int i = 0; i < K; i++) {
			int tmp[][] = cpy(i, arr[i].length, arr[i][0].length);
			for (int d = 0; d < 4; d++) {
				if (d != 0) {
					// 돌리기
					tmp = spin(tmp);
				}
				// 붙이기
				if(attach(tmp)) {
					break;
				}
			}
		}
		int sum=0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==1)
					sum++;
			}
		}
		System.out.println(sum);
	}

	static boolean attach(int tmp[][]) {
		int h=tmp.length;
		int w=tmp[0].length;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				boolean flag = true;
				int cpyMap[][] = new int[N][M];
				//복사
				for(int ii=0; ii<N; ii++) {
					for(int jj=0; jj<M; jj++) {
						cpyMap[ii][jj] = map[ii][jj];
					}
				}

				out:for(int r=0; r<h; r++) {
					for(int c=0; c<w; c++) {
						int nr = i+r;
						int nc = j+c;
						if(nr<0 || nr>=N || nc<0 || nc>=M) { 
							flag = false;
							break out;
						}
						if(cpyMap[nr][nc]==0 && tmp[r][c]==1) {
							cpyMap[nr][nc]=1;
						}else if((cpyMap[nr][nc]==0 && tmp[r][c]==0) || (cpyMap[nr][nc]==1 && tmp[r][c]==0)) {
							continue;
						}else {
							flag = false;
							break out;
						}
					}
				}
				if(flag) {
					//오리지널에 복사 그리고 리턴
					for(int ii=0; ii<N; ii++) {
						for(int jj=0; jj<M; jj++) {
							map[ii][jj] = cpyMap[ii][jj];
						}
					}
					return true;
				}
			}
		}
		return false;
	}

	static int[][] spin(int a[][]) {
		int h = a.length;
		int w = a[0].length;
		int ret[][] = new int[w][h];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				ret[j][h - i - 1] = a[i][j];
			}
		}
		return ret;
	}

	static int[][] cpy(int k, int h, int w) {
		int tmp[][] = new int[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				tmp[i][j] = arr[k][i][j];
			}
		}
		return tmp;
	}
}

5. 느낀점

한자리 씩 비교해 주기 떄문에 시간복잡도가 상당하다.

다른 풀이를 연구해 봐야겠다.