https://www.acmicpc.net/problem/18808
18808번: 스티커 붙이기
혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연
www.acmicpc.net
코드설명
구현(implementation) + 시뮬레이션(Simulation) 문제입니다.
이 문제의 경우 문제에 대한 이해가 필요합니다.
혜윤이가 스티커를 붙이는 방법은 다음과 같다.
- 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
- 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
- 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
- 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
위를 보면, 스티커를 가장 많이 붙이는 방식이 아닌, 스티커를 위의 주어진대로 붙였을때 붙여진다면 해당 사항이 정답입니다.
처음에는 모든 경우를 완전탐색하는 경우, 즉 최대값을 구하기 위해 진행하다가 해당 과정으로 진행할경우 올바르게 정답이 나오지 않습니다. 또한 완전탐색으로 진행하며 코드복잡도가 올라가서 구현하는데 시간이 많이 걸렸습니다.
또한, 스티커를 붙이는 함수인 stickerOn 함수를 생성함으로써, 따로 flag 변수를 사용해서 종료시키지 않아도됩니다.
코드로보면, 아래의 코드에서 만약 stickerOn 함수를 사용하지 않았다면 flag 변수를 활용하여 붙였는지 안붙였는지 체크하고, 붙였다면 종료하는 로직을 추가했어야 했을 것 입니다.
//만약 범위안에 존재한다면, stickerOn 메소드로 붙일 수 있는지 확인하고 붙인다.
if( i + sticker.length <= N && j + sticker[0].length <= M ) {
if( stickerOn(i, j, sticker.length, sticker[0].length, sticker) == true) { //만약 붙였다면 종료시시킵니다.
return ;
}
}
문제에서 유의해야할점은 스티커의 범위처리입니다.
아래의 주석과 같이 length는 1부터 시작하고, N의 Size는 0부터 시작하도록 처리했으므로 > N으로 처리해야만 올바르게 범위를 연산합니다.
//처음에 i + tempSticker.length >= N 으로 처리했었는데, 생각해보면 스티커의 행의 길이는 0부터 시작하지 않고 1부터 시작하므로 > N 입니다.
if( i + tempSticker.length < 0 || i + tempSticker.length > N || j + tempSticker[0].length < 0 || j + tempSticker[0].length > M) {
stickerSuccessFlag = false;
continue;
}
문제에서 하나의 스티커 종류를 사용한지 아닌지 처리하는 부분은 KindSuccesssFlag 로 처리하고,
스티커 자체의 성공은 stickerSuccessFlag 로 처리하였습니다.
simulate 함수 내에서 각 Map[][]의 모든 요소를 돌면서 모든 스티커를 붙일것인데, 이떄 적절하게 종료조건을 처리해야만이미 붙인 같은 종류의 사용한 스티커는 붙이지 않도록 처리할 수 있고,
성공한 스티커의 경우 올바르게 붙인 후에 해당 스티커는 더이상 붙여지지 않도록 처리할 수 있습니다.
특히 아래의 코드에서 kindSuccessFlag == true라면 바로 중지하도록 처리하는 부분이 중요합니다. 이를 통해 1번 스티커를 한번 붙였다면 더 이상 붙이지 않도록 처리합니다.
public static void simulate(int level) {
...
...
for(int i=0; i<N; i++) {
for(int j= 0; j<M; j++) {
if(kindSuccessFlag == true)
break;
stickerSuccessFlag = true; //각 스티커를 새로 계산할 것 입니다.
...
...
문제에서 Sticker의 Size를 올바르게 Rotate 하게 하기 위해 각 Size에 맞도록 처리해주어야하는데
이떄 이전 모양(dir - 1)의 배열인덱스를 처리하는 과정과 같은 부분에서 실수하였습니다.
이럴떄는 전체적으로 beforeSticker를 선언하여 처리한다면 실수를 줄일 수 있다고 생각합니다.
public static void makeStickerRotate(int stickerKind) {
for(int dir = 1; dir < 4; dir++) {
int[][] beforeSticker = sticker[stickerKind][dir-1];
int beforeRowLength = beforeSticker.length;
int beforeColLength = beforeSticker[0].length;
//사이즈는 이전 모양의 회전Row Col 로 설정합니다.
sticker[stickerKind][dir] = new int[beforeColLength][beforeRowLength];
for(int i=0;i<beforeRowLength;i++) {
for(int j=0;j<beforeColLength;j++) {
//이 sticker[stickerKind][dir - 1][i][j] 부분에서 dir -1 로 하지 않고, dir로 햇어서 안됬음, 즉 이전 스티커로 처리하지 않아서 오류났었습니다.
sticker[stickerKind][dir][j][beforeRowLength - i - 1] = sticker[stickerKind][dir - 1][i][j];
}
}
}
}코드
스티커를 붙일 수 있다면 바로 붙이면서 작업해나간다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K;
public static int[] arr;
public static boolean[][] map;
public static int answer = 0;
public static ArrayList<int[][]> sticker = new ArrayList<int[][]>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new boolean[N][M];
for(int i=0;i<K;i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
sticker.add(new int[r][c]);
for(int j=0;j<r; j++) {
st = new StringTokenizer(br.readLine());
for(int k=0;k<c;k++) {
sticker.get(i)[j][k] = Integer.parseInt(st.nextToken());
}
}
}
for(int i=0;i<K;i++) {
simulate(sticker.get(i));
}
System.out.println(answer);
}
public static void simulate(int[][] sticker) {
for(int dir = 0; dir < 4; dir ++) {
if(dir != 0)
sticker = rotate(sticker);
for(int i=0; i<N;i++) {
for(int j=0; j<M; j++) {
//만약 범위안에 존재한다면, stickerOn 메소드로 붙일 수 있는지 확인하고 붙인다.
if( i + sticker.length <= N && j + sticker[0].length <= M ) {
if( stickerOn(i, j, sticker.length, sticker[0].length, sticker) == true) { //만약 붙였다면 종료시시킵니다.
return ;
}
}
}
}
}
}
public static boolean stickerOn(int i, int j, int sR, int sC, int[][] sticker) {
//스티커를 붙일 수 있는지 확인.
for(int k=i; k< i + sticker.length; k++) {
for(int h=j; h< j + sticker[0].length; h++) {
if( sticker[k - i][h - j] == 1 && map[k][h] == true) { //불가능하다.
return false;
}
}
}
for(int k=i; k< i + sticker.length; k++) {
for(int h=j; h< j + sticker[0].length; h++) {
if(sticker[k-i][h-j] == 1) {
map[k][h] = true;
answer += 1;
}
}
}
return true;
}
public static int[][] rotate(int[][] sticker) {
int[][] newSticker = new int[sticker[0].length][sticker.length];
for(int i=0; i<sticker.length; i++) {
for(int j=0; j<sticker[0].length; j++) {
newSticker[j][ sticker.length - i - 1] = sticker[i][j];
}
}
return newSticker;
}
}
다른방법으로 풀어본 코드.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N,M, K;
public static boolean[][] map;
public static int[][][][] sticker;
public static int answer = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new boolean[N][M];
sticker = new int[K][4][][];
for(int k=0;k<K;k++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
sticker[k][0] = new int[r][c];
for(int row=0;row<r;row++) {
st = new StringTokenizer(br.readLine());
for(int col=0;col<c;col++) {
sticker[k][0][row][col] = Integer.parseInt(st.nextToken());
}
}
}
for(int k=0;k<K;k++) {
makeStickerRotate(k);
}
simulate(0);
for(int i=0; i<N;i++) {
for(int j=0;j<M;j++) {
if(map[i][j] == true) {
answer += 1;
}
}
}
System.out.println(answer);
}
public static void simulate(int level) {
for(int kind = 0; kind < K; kind++) {
boolean kindSuccessFlag = false;
for(int dir = 0; dir < 4; dir++) {
boolean stickerSuccessFlag = true;
if(kindSuccessFlag == true)
break;
int[][] tempSticker = sticker[kind][dir];
for(int i=0; i<N; i++) {
for(int j= 0; j<M; j++) {
if(kindSuccessFlag == true)
break;
stickerSuccessFlag = true; //각 스티커를 새로 계산할 것 입니다.
//만약 Size가 넘어가면 애초에 불가능합니다.
//처음에 i + tempSticker.length >= N 으로 처리했었는데, 생각해보면 스티커의 행의 길이는 0부터 시작하지 않고 1부터 시작하므로 > N 입니다.
if( i + tempSticker.length < 0 || i + tempSticker.length > N || j + tempSticker[0].length < 0 || j + tempSticker[0].length > M) {
stickerSuccessFlag = false;
continue;
}
for(int r=0;r<tempSticker.length;r++) {
for(int c=0;c<tempSticker[r].length;c++) {
//겹치는 경우가 있으면 실패입니다.
if( map[i + r][j + c] == true && tempSticker[r][c] == 1) {
stickerSuccessFlag = false;
}
}
}
//만약 위의 검사 후 성공한다면, 스티커를 실제로 붙여줍니다.
if(stickerSuccessFlag == true) {
for(int r=0;r<tempSticker.length;r++) {
for(int c=0;c<tempSticker[r].length;c++) {
if(tempSticker[r][c] == 1) {
map[i+r][j+c] = true;
}
}
}
//해당 dir를 성공했으니, 해당 스티커는 더 이상 안붙입니다.
kindSuccessFlag = true;
break;
}
}
}
}
}
}
public static void makeStickerRotate(int stickerKind) {
for(int dir = 1; dir < 4; dir++) {
int[][] beforeSticker = sticker[stickerKind][dir-1];
int beforeRowLength = beforeSticker.length;
int beforeColLength = beforeSticker[0].length;
//사이즈는 이전 모양의 회전Row Col 로 설정합니다.
sticker[stickerKind][dir] = new int[beforeColLength][beforeRowLength];
for(int i=0;i<beforeRowLength;i++) {
for(int j=0;j<beforeColLength;j++) {
//이 sticker[stickerKind][dir - 1][i][j] 부분에서 dir -1 로 하지 않고, dir로 햇어서 안됬음, 즉 이전 스티커로 처리하지 않아서 오류났었습니다.
sticker[stickerKind][dir][j][beforeRowLength - i - 1] = sticker[stickerKind][dir - 1][i][j];
}
}
}
}
public static void print() {
for(int kind = 0; kind < K; kind++) {
System.out.println("sticker kind:"+kind);
for(int dir = 0; dir < 4; dir++) {
System.out.println("===dir :"+dir);
for(int i=0; i<sticker[kind][dir].length;i++) {
for(int j=0; j<sticker[kind][dir][i].length;j++) {
System.out.print(sticker[kind][dir][i][j]+" ");
}
System.out.println();
}
System.out.println();
}
}
}
}
이렇게 하면 모든 경우의 수를 다 찾아보게 되서 안된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K;
public static int[] arr;
public static boolean[][] map;
public static int answer = 0;
public static ArrayList<int[][]> sticker = new ArrayList<int[][]>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new boolean[N][M];
for(int i=0;i<K;i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
sticker.add(new int[r][c]);
for(int j=0;j<r; j++) {
st = new StringTokenizer(br.readLine());
for(int k=0;k<c;k++) {
sticker.get(i)[j][k] = Integer.parseInt(st.nextToken());
}
}
}
// simulate(0, map);
// int[][] test = sticker.get(3);
// for(int i=0;i<test.length;i++) {
// for(int j=0;j<test[0].length;j++) {
// System.out.print(" "+test[i][j]);
// }
// System.out.println();
// }
// System.out.println("===============");
// test = rotate(test);
// for(int i=0;i<test.length;i++) {
// for(int j=0;j<test[0].length;j++) {
// System.out.print(" "+test[i][j]);
// }
// System.out.println();
// }
// System.out.println("===============");
// test = rotate(test);
// for(int i=0;i<test.length;i++) {
// for(int j=0;j<test[0].length;j++) {
// System.out.print(" "+test[i][j]);
// }
// System.out.println();
// }
// System.out.println("===============");
// test = rotate(test);
// for(int i=0;i<test.length;i++) {
// for(int j=0;j<test[0].length;j++) {
// System.out.print(" "+test[i][j]);
// }
// System.out.println();
// }
simulate(0);
System.out.println(answer);
}
public static void simulate(int level) {
if(level == K) { //만약 모든 스티커를 다 붙였다면,
System.out.println("level============================="+level);
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
System.out.print(" "+map[i][j]);
}
System.out.println();
}
System.out.println();
return ;
}
boolean[][] mapCopy = new boolean[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
mapCopy[i][j] = map[i][j];
}
}
//여기서 알아야할점은, 순서대로 스티커를 못붙이면 다음 simulate 재귀로 못들어간다.
int[][] stickerArr = sticker.get(level);
for(int dir = 0; dir<4; dir++) {
stickerArr = rotate(stickerArr);
System.out.println("======================Sticker Rotate======================");
for(int i=0; i<stickerArr.length; i++) {
for(int j=0; j<stickerArr[0].length; j++) {
System.out.print(" "+stickerArr[i][j]);
}
System.out.println();
}
System.out.println("==");
boolean flag = false; //만약 한번이라도 가장 빨리 성공한다면 바로 더이상 작업하지 않습니다.
boolean workFlag = false; //어디에도 작업하지 못한다면 그냥 다음껄로 넘깁니다.
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
flag = false;
//1. 스티커를 Map에 찍을 수 있는지 확인하는 함수가 필요합니다.
//1-1.우선 범위가 벗어나는지 먼저 확인합니다.
int stickerRowLength = stickerArr.length + i;
int stickerColLength = stickerArr[0].length + j;
//노트북의 길이보다 스티커의 길이가 작아야만 합니다.
if( N > stickerRowLength - 1 && M > stickerColLength - 1) {
//Map에 실제로 붙일 수 있는지 확인합니다.
for(int k=i; k<i + stickerArr.length; k++) {
for(int h=j; h<j + stickerArr[0].length; h++) {
// System.out.println("k:"+k+"h:"+h+"level:"+level);
if(stickerArr[k - i][h - j] == 1 && map[k][h] == true) { //만약 스티커 존재칸에 하나라도 "이미 True"라면 실패입니다.
flag = true;
break;
}
}
if(flag==true) break;
}
//만약 flag == false라면 붙일 수 있습니다.
if(flag == false) {
workFlag = true;
for(int k=i; k<i + stickerArr.length; k++) {
for(int h=j; h<j + stickerArr[0].length; h++) {
if(stickerArr[k - i][h - j] == 1)
map[k][h] = true;
}
}
// System.out.println("simulate level + 1=============================");
// for(int k=0; k<N; k++) {
// for(int h=0; h<M; h++) {
// System.out.print(" "+map[k][h]);
// }
// System.out.println();
// }
// System.out.println();
simulate(level + 1);
//map은 재귀가 끝났으니 원상복구
for(int k=0;k<N;k++) {
for(int h=0;h<M;h++) {
map[k][h] = mapCopy[k][h];
}
}
}
}
}
if(flag == false) break;
}
if(workFlag == false) {
simulate(level + 1);
}
}
}
public static int[][] rotate(int[][] sticker) {
int[][] newSticker = new int[sticker[0].length][sticker.length];
// for(int i=0; i<sticker.length; i++) {
// for(int j=0; j<sticker[0].length; j++) {
// System.out.print(" "+sticker[i][j]);
// }
// System.out.println();
// }
// System.out.println("==");
for(int i=0; i<sticker.length; i++) {
for(int j=0; j<sticker[0].length; j++) {
// newSticker[sticker.length - j - 1][ sticker.length - i - 1] = sticker[i][j];
newSticker[j][ sticker.length - i - 1] = sticker[i][j];
}
}
// for(int i=0; i<newSticker.length; i++) {
// for(int j=0; j<newSticker[0].length; j++) {
// System.out.print(" "+newSticker[i][j]);
// }
// System.out.println();
// }
return newSticker;
}
}
처음에 주어진 스티커를 가변배열로 선언해본것입니다.
//[스티커 종류 : 4][각 스티커 회전방향 : ?][스티커 개수][스티커 row, col, : 2]
public static int[][][][] sticker = new int[][][][] //아무것도 선언안해야작동하네
{
{ //0번쨰 스티커
{ //회전 1
{0, 0}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}
},
{ //회전 2
{0, 0}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}
}
},
{ //1번째 스티커,
{
{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 3}
},
{
{0, 1}, {1, 1}, {2, 1}, {3, 0}, {3, 1}, {4, 1}
},
{
{0, 1}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}
},
{
{0, 0}, {1, 0}, {1, 1}, {2, 0}, {3, 0}, {4, 0}
}
},
{ //2번쨰 스티커
{
{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 2}
},
{
{0, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}
},
{
{0, 0}, {0, 2}, {1, 0}, {1, 1}, {1, 2}
},
{
{0, 0}, {0, 1}, {1, 0}, {2, 0}, {2, 1}
}
},
{ // 3번째스티커
{
{0, 0}, {1, 0}, {1, 1}, {1, 2}, {2, 0}
},
{
{0, 0}, {0, 1}, {0, 2}, {1, 1}, {2, 2}
},
{
{0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 2}
},
{
{0, 1}, {1, 1}, {2, 0}, {2, 1}, {2, 2}
}
}
};