백준 18808 <스티커 붙이기>

문제만 잘 읽는다면 많은 사람들이 쉽게 풀 수 있을 만한 전형적인 시뮬레이션 문제이다. 

 

이 문제를 푸는데 가장 중요한것은 총 두 가지이다.

1. 첫 번째는 스티커를 순서대로 붙이고 4방향으로 돌려서 붙여지지 않는 스티커는 넘어간다.
2. 두 번째는 스티커를 가장 위쪽, 왼쪽에서부터 차례대로 확인하는 문제이다.

이 두 가지 방법만 잘 교려 해 준다면 쉽게 접근할 수 있는 문제이다.

 

기본적으로 이 문제의 최대 시간을 고려한다면 맵의 길이가 40*40이고 모든 칸을 검색한다 해도 30만이 안 되는 값이다. 4방향으로 한다고 고려하면 120만 스티커의 개수인 100을 곱해도 1억 2 천 번이기 때문에 해결할 수 있는 문제이다.

 

일단 나는 기본적으로

크기가 다른 배열을 넣어주기 위해서 어레이 리스트를 사용해서 2중 배열을 넣어주었다.

 

나는 기본적으로 스티커의 개수만큼 재귀를 돌 go함수와 스티커를 회전시켜 줄 change 함수, 스티커를 붙일 수 있는지 확인하는 can 함수 세 개의 함수를 사용했다.

 

함수를 사용하는데 장점은 디버깅을 돌릴 때 오류가 어디서 생겼는지 쉽게 알 수 있다는 장점이 있다!

 

 

스티커 개수만큼 회전할 go함수이다. 개수가 총 스티커 갯수가 되면 map에 있는 1을 더해 그 값을 결과로 출력하도록 했다.

 

4방향으로 회전을 하여 만약 can에서 true가 나온다면 다음으로 넘어가고 재귀 함수가 끝나면 return을 해주는 방식으로 구현했다. 밑에 따로 있는 go는 4방향으로 회전해도 스티커가 붙여지지 않을 경우 버리고 다음으로 넘어가는 경우이다.

 

changd 함수는 말 그대로 90 도를 회전하는 함수이다. 이 부분에서 회전을 시키는 게 익숙지 않아서 실수도 있었지만 비교적 쉬운 코드이다. 하나의 배열을 새로 생성하고 받아온 배열의 열을 새로운 배열의 행에 이전의 행을 새로운 배열의 열 사이즈로 맞추고 받아오나 return 하는 것이다.

 

확인 방법은 그림에서 처럼 3*2 행렬을 7*4 행렬을 전체 확인하기 위해서 0행부터 시작하므로 7-3 =4 행까지 4-2 =2렬 을 검사하면서 서로 위치하는 곳이 1이 있다면 flag를 false로 바꿔 다음을 탐색하도록 했습니다!

 

기본적으로 알고리즘의 흐름만 알고 구현을 할 수 있다면 풀 수 있는 문제였습니다!.

 

전체 코드

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

public class Main {

	static int map[][],n,m,k,sum;
	static ArrayList<int[][]> a=new ArrayList<int[][]>();

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(kb.readLine());
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		map=new int[n][m];
		for(int i=0;i<k;i++) {
			st=new StringTokenizer(kb.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			int map1[][]=new int[x][y];
			for(int j=0;j<x;j++) {
				st=new StringTokenizer(kb.readLine());
				for(int h=0;h<y;h++) {
					map1[j][h]=Integer.parseInt(st.nextToken());
				}
			}
			a.add(map1);
		}
		go(0);
		
		System.out.println(sum);
	}
	public static void go(int o) {
		if(k==o) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					sum+=map[i][j];
				}
			}
			return;
		}
		int find[][]=a.get(o);
		for(int i=0;i<4;i++) {
			if(can(find,o)) {
				go(o+1);
				return;
			}
			find=change(find);
		}
		go(o+1);
	}
	public static int[][] change(int num[][]){
		int next[][]=new int[num[0].length][num.length];
		
		for(int i=0;i<next.length;i++) {
			for(int j=0;j<next[0].length;j++) {
				next[i][j]=num[next[0].length-1-j][i];
			}
		}
		
		return next;
	}
	public static boolean can (int num[][],int k) {
		for(int i=0;i<=n-num.length;i++) {
			for(int j=0;j<=m-num[0].length;j++) {
				boolean flag=true;
				
				for(int h=i;h<i+num.length;h++) {
					for(int w=j;w<j+num[0].length;w++) {
						if(map[h][w]==1&&num[h-i][w-j]==1) {
							flag=false;
							break;
						}
					}
					if(flag==false) {
						break;
					}
				}
				if(flag) {
					for(int h=i;h<i+num.length;h++) {
						for(int w=j;w<j+num[0].length;w++) {
							if(map[h][w]==0&&num[h-i][w-j]==1) {
								map[h][w]=1;
							}
						}
					}
					return true;
				}
			}
		}
		return false;
	}
	

}