Do You Coding?
[BOJ] 백준 18808번: 스티커 붙이기 (JAVA) 본문
- 문제 출처 : https://www.acmicpc.net/problem/18808
1. 생각
격자로 된 모눈종이에 스티커들이 있고, 이 스티커들을 노트북에 붙이는 문제이다.
방법은 다음의 규칙을 따르는데,
1) 스티커를 붙일 수 있는 가장 좌상단에 스티커를 붙힌다. (상단이 우선, 같은 높이에서는 왼쪽이 우선)
2) 붙일 수 있는 위치가 없으면, 90도 회전하고 다시 1번 방법으로 돌아간다.
3) 0도 / 90도 / 180도/ 270도 모두 붙일 수 없으면, 해당 스티커는 버린다.
가능한 많은 스티커를 붙이는 경우의 수의 문제거나, 붙히는 순서가 고정되어있지 않았다면 훨씬 복잡했을 수도 있지만,
순서가 정해져있고, 붙이는 위치도 좌상단으로 고정되어있어 편하게 규칙대로 짜면 될 것 같다고 생각했다.
하지만 생각보다 격자 2차원 배열을 돌리는 문제를 처음 풀어봐서 좀 어지러웠다.
2. 난관 & 해결방법
문제 해결 순서)
| 1. 스티커를 입력 받는다. 2. 스티커를 0도, 90도, 180도, 270도 회전 기준으로 반복문을 돌며 붙힐 스티커의 상태를 저장한다. 3. 해당 스티커의 상태가 완전탐색을 통해 노트북에 붙힐 수 있는지 판단한다. 4. 붙힐 수 있으면 다음 스티커를 입력받고, 붙힐 수 없으면 다음 회전 방법으로 스티커의 상태를 바꾸고 반복한다. 5. 붙히지 못하면 스티커를 버리고 다음 스티커로 넘어가고, 모든 스티커를 순회하고 나서 스티커가 붙은 공간 수를 센다. |
위의 순서대로 문제를 해결하기 위해 다음과 같은 로직들을 활용했다.
static variables
static int N; // 노트북 세로 길이
static int M; // 노트북 가로 길이
static int K; // 스티커 개수
static int r; // 현재 스티커의 세로 길이
static int c; // 현재 스티커의 가로 길이
static int num; // 스티커가 붙혀진 격자 공간의 수
static int[][] notebook; // 스티커가 붙혀질 노트북 공간
static int[][] stickerNew; // 붙힐 스티커 (입력으로 받은 스티커를 방향을 돌린 상태 저장)
public static void main(String[] args)
for (int k = 0; k < K; ++k)
{
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
int[][] sticker = new int[r][c];
for (int i = 0; i < r; ++i)
{
st = new StringTokenizer(br.readLine());
for (int j = 0; j < c; ++j)
{
sticker[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int d = 0; d < 4; ++d)
{
if (matching(sticker, d))
break;
}
}
main에서 입력을 제외한 메인로직을 담당하는 부분이다.
for문은 총 K번을 돌게 설정해두었고, 위의 변수들에서 보았듯이 이는 스티커 개수를 의미한다.
따라서 스티커를 하나 입력 받고 바로 스티커를 붙히는 로직으로 향한다.
그리고 스티커가 붙혀지는지 방향을 돌려가면서 확인하기 위해,
for문을 내부에서 더 돌아서, 회전방향을 뜻할 d 라는 변수를 matching함수에 함께 매개변수로 넣어준다.
static boolean matching(int[][] sticker, int d)
static boolean matching(int[][] sticker, int d) {
switch (d) {
case 0: // 0
{
stickerNew = sticker;
return bruteforce(r, c);
}
case 1: // 90
{
stickerNew = new int[c][r];
for (int i = 0; i < c; ++i)
for (int j = 0; j < r; ++j)
stickerNew[i][j] = sticker[r - 1 - j][i];
return bruteforce(c, r);
}
case 2: // 180
{
stickerNew = new int[r][c];
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
stickerNew[i][j] = sticker[r - 1 - i][c - 1 - j];
return bruteforce(r, c);
}
case 3: // 270
{
stickerNew = new int[c][r];
for (int i = 0; i < c; ++i)
for (int j = 0; j < r; ++j)
stickerNew[i][j] = sticker[j][c - 1 - i];
return bruteforce(c, r);
}
default:
return false;
}
}
매개변수로 받아온 d에 따라, switch문을 넣어주는 방식으로 matching 함수를 만들었다.
0이면 sticker를 받아온 그대로 붙혀보는 시도를 하고,
1이면 sticker를 우측으로 90도 돌려 붙혀보는 시도를 하고,
2이면 sticker를 우측으로 180도 돌려 붙혀보는 시도를 하고,
3이면 sticker를 우측으로 270도 돌려 붙혀보는 시도를 한다.
여기서 행과 열의 값을 컨트롤하는게 쉽지 않았다.
수학적으로 생각하면 쉬운 것도 같은데, 이런 문제를 많이 안풀어봐서 좀 복잡하게 느껴졌다.
우선 90도는 어떻게 생각하면 좋을까?
이런 행렬 회전에서는 크게 3가지의 방법을 섞어서 이용해야 원하는 대로 컨트롤 할 수 있는데,
행의 수를 R, 열의 수를 C로, 좌표는 ( r , c ) 로 생각하고 진행하도록 하겠다.
1번째는 '좌우반전' 이다.
위처럼 좌우 반전을 하는 것인데,
( r , c ) 가 ( r , (C - 1) - c) 이 되면 좌우가 반전이 된다.
1행1열이 1행5열이 되고, 1행2열이 1행4열이 되고, 이런식으로 열의 값이 반전되므로, c값이 뒤집히는 것이다.
ex) (1,3) 위치가 좌우반전되면, (1, (5 - 1) - 3) 으로 (1, 1) 이다. [ 그림에서 9의 위치 ]
2번째는 '상하반전' 이다.
좌우 반전과 비슷하게,
(r, c) 가 ((R - 1) - r, c) 이 되면 상하가 반전이 된다.
1행1열이 3행1열이 되고, 1행2열이 3행2열이 되고, 행의 값이 반전되는 모습이므로, r 값이 뒤집힌다.
ex) (2, 1) 위치가 상하반전되면, ((3 - 1) - 2, 1) 으로, (0, 1) 이다. [ 그림에서 12의 위치 ]
3번째가 중요한 '전치' 이다!
전치란, 행과 열의 값을 바꾸는 것을 뜻하는데,
(r, c) 가 (c, r) 이 되면 행과 열의 값이 바뀌어 전치가 된다.
값 자체는 서로 바꾸면 되어서 단순하지만 값이 어떤식으로 이동되는지는 이해하기가 까다로울 수 있다.
함께 공부하는 친구가 쏙쏙 이해되게 알려준 방법인데,
휴대폰을 뒤집으면서 방향도 우측으로 90도 돌리면 전치가 되는 것과 동일하다고 알려줬다.
위 그림처럼 행렬이 뒤집히면서 방향도 90도 돌리면 전치가 된 값과 동일하다.
3 * 5 행렬은 5 * 3 행렬이 되며, 위치는 기존 좌표 r, c에서 c, r로 바뀐다.
ex) (1, 3) 위치가 전치되면, (3, 1) 으로 이동한다. [ 그림에서 9의 위치 ]
위 행렬의 3가지 움직임을 이용해서, 우측으로 90도를 뒤집는 이동을 하려면 어떻게 할까?
위에서 본 휴대폰 뒤집기로 비유해보면,
휴대폰을 뒤집으면서 돌린 뒤, 그 휴대폰을 그냥 앞뒤만 뒤집으면 된다!
따라서 전치 + 좌우반전 을 하게 되면 우측으로 90도 회전한 행렬이 되는 것이다.
180도, 270도도 3가지의 이동을 활용하면 쉽게 만들 수 있음을 생각해낼 수 있을 것이다!!
(90도 = 전치 + 좌우반전 / 180도 = 좌우반전 + 상하반전 / 270도 = 전치 + 상하반전)
그럼 위의 코드에서 보면 이를 활용한 코드로 만들어졌음을 알 수 있다.
static boolean bruteforce(int row, int col)
static boolean bruteforce(int row, int col) {
for (int i = 0; i < N - row + 1; ++i)
{
for (int j = 0; j < M - col + 1; ++j)
{
if (compareSticker(row, col, i, j))
{
for (int k = 0; k < row; ++k)
{
for (int l = 0; l < col; ++l)
{
if(stickerNew[k][l] == 1)
{
notebook[i + k][j + l] = stickerNew[k][l];
num ++;
}
}
}
return true;
}
}
}
return false;
}
이 완전 탐색 코드는 조금 부끄러울 정도로 for문과 if문을 도배해뒀는데,
메소드를 하나 더 빼내어 적용시키는게 좋을 듯 하지만, 구현 당시에는 한번에 만드는 게 편해서 이렇게 작성했다.
노트북의 크기에 스티커가 들어갈 수 있는 좌표 기준으로 탐색하며,
compareSticker() 메소드를 통해 붙일 수 있음이 확인 되면 붙이는 작업을 하게 되며, true를 return 해준다.
(compareSticker 메소드는 전체 코드에서 확인할 수 있는데 단순히 새로 붙힐 스티커와 현재 노트북을 비교해서
스티커가 겹치는지 아닌지만 true, false로 반환해주는 메소드이다.)
3. 코드 및 결론
[ 전체 코드 ]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int M;
static int K;
static int r;
static int c;
static int num;
static int[][] notebook;
static int[][] stickerNew;
static boolean compareSticker(int row, int col, int i, int j)
{
for (int k = 0; k < row; ++k)
{
for (int l = 0; l < col; ++l)
{
if (stickerNew[k][l] == 1)
{
if (notebook[i + k][j + l] == 1)
return false;
else
continue;
}
}
}
return true;
}
static boolean bruteforce(int row, int col) {
for (int i = 0; i < N - row + 1; ++i)
{
for (int j = 0; j < M - col + 1; ++j)
{
if (compareSticker(row, col, i, j))
{
for (int k = 0; k < row; ++k)
{
for (int l = 0; l < col; ++l)
{
if(stickerNew[k][l] == 1)
{
notebook[i + k][j + l] = stickerNew[k][l];
num ++;
}
}
}
return true;
}
}
}
return false;
}
static boolean matching(int[][] sticker, int d) {
switch (d) {
case 0: // 0
{
stickerNew = sticker;
return bruteforce(r, c);
}
case 1: // 90
{
stickerNew = new int[c][r];
for (int i = 0; i < c; ++i)
for (int j = 0; j < r; ++j)
stickerNew[i][j] = sticker[r - 1 - j][i];
return bruteforce(c, r);
}
case 2: // 180
{
stickerNew = new int[r][c];
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
stickerNew[i][j] = sticker[r - 1 - i][c - 1 - j];
return bruteforce(r, c);
}
case 3: // 270
{
stickerNew = new int[c][r];
for (int i = 0; i < c; ++i)
for (int j = 0; j < r; ++j)
stickerNew[i][j] = sticker[j][c - 1 - i];
return bruteforce(c, r);
}
default:
return false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
notebook = new int[N][M];
for (int k = 0; k < K; ++k) // 스티커 개수
{
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
int[][] sticker = new int[r][c];
for (int i = 0; i < r; ++i)
{
st = new StringTokenizer(br.readLine());
for (int j = 0; j < c; ++j)
{
sticker[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int d = 0; d < 4; ++d)
{
if (matching(sticker, d))
break;
}
}
System.out.println(num);
}
}
[ 결론 ]
구현문제를 이렇게 분석적으로 게시글을 써본 건 처음이다.
그동안 구현문제를 머리 부딪히면서 그냥 푼 것 같은데,
체계적으로 정리하면서 풀면 더욱 단순화할 수 있다는 것을 깨닫고,
실제로 문제를 풀때도 더 체계화 해서 하나씩 작은 문제로 만들어서 쳐낼 수 있어야함을 느끼게 된 문제이다.
또한 2차원 행렬에 대한 이해도를 많이 늘릴 수 있던 것 같다.
전치와 반전 들을 잘 활용해보자!
'CS & Engineering > Algorithm' 카테고리의 다른 글
| [BOJ] 백준 2579번: 계단 오르기 (JAVA) (0) | 2025.10.29 |
|---|---|
| [BOJ] 백준 15683번: 감시 (JAVA) (0) | 2025.10.24 |
| [BOJ] 백준 1238번: 파티 (JAVA) (0) | 2025.10.20 |
| [BOJ] 백준 11779번: 최소비용 구하기 2 (JAVA) (0) | 2025.10.20 |
| [BOJ] 백준 10816번: 숫자 카드 2 (C++) (0) | 2025.04.28 |
