주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
.....
접근 방법
이 문제에 핵심
1. 스티커는 상하좌우 연결되어 있으며 불필요한 행이나 열이 존재하지 않습니다.
2. 혜운이가 스티커를 붙이는 과정은 문제에서 자세히 설명하고 있습니다.
3. 스티커는 K개가 주어지며 회전을 진행할 수 있습니다.
4. 스티커를 과정대로 붙일 때 모눈종이에 붙은 칸의 수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 혜윤이가 스티커를 처리하는 과정을 순차적으로 진행합니다.
3. 과정이 끝난 뒤 스티커를 붙인 칸의 수를 결과로 출력합니다.
스티커를 붙이는 과정
1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
→ 회전하지 않고(0도)로 우선적으로 스티커를 떼어본다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
→ 스티커를 붙일 위치를 정한다.
→ 우선순위는 가장 위쪽, 가장 왼쪽
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
→ 회전을 진행(오른쪽으로 90도)한 뒤 2번을 반복!
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
→ 회전을 통해서도 스티커를 붙이지 못하면 해당 스티커는 버린다.
스티커 회전(배열 돌리기)
| 1 | 1 | 1 |
| 0 | 0 | 1 |
90도로 돌리기
| 0 | 1 |
| 0 | 1 |
| 1 | 1 |
(0, 0) → (0, 1)
(0, 1) → (1, 1)
(1, 1) → (1, 0)
점화식
(i, j) → (j, R - 1 - i)
R : 열의 길이
예제입력 2.
1. 입력된 정보를 저장합니다.
N : 1
M : 3
K : 3
1번째 스티커(R : 2, C : 3)
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2번째 스티커(R : 1, C : 1)
| 1 |
3번째 스티커(R : 3, C : 1)
| 1 |
| 1 |
| 1 |
2. 혜윤이가 스티커를 처리하는 과정을 순차적으로 진행합니다.
붙일 모눈종이
1번째 스티커 붙이기
| 1 | 0 | 0 |
| 1 | 1 | 1 |
→ 붙일 모눈종이보다 스티커가 커서 붙일 수가 없습니다
2번째 스티커 붙이기
| 1 |
→ 회전하지 않고, 우선순위가 높은 (0, 0)에 붙히기
붙일 모눈종이
| 1 |
3번째 스티커 붙이기
| 1 |
| 1 |
| 1 |
→ 기본 상태에서는 스티커를 붙일 수 없습니다. 모눈종이에 벗어나기 때문입니다.
3번째 스티커 회전
| 1 | 1 | 1 |
→ 기본 상태에서는 스티커를 붙일 수 없습니다. (0, 0)에 2번째 스티커가 존재하기 때문입니다.
→ 180도, 270도를 회전해도 (0, 0)에 존재하는 스티커나 모눈종이에 벗어나기 때문에 해당 스티커를 붙일 수 없습니다.
과정 종료!
3. 과정이 끝난 뒤 스티커를 붙인 칸의 수를 결과로 출력합니다.
| 1 |
1을 결과로 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 N, M, K와 각 스티커의 정보를 저장합니다.
- search 함수를 이용하여 스티커를 붙이는 과정을 진행합니다.
- 과정이 끝난 뒤 모눈종이에 스티커가 붙인 칸 수를 BufferedWriter에 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
- search함수는 혜윤이가 스티커를 붙이는 과정을 순차적으로 진행되도록 구현하였습니다.
- rotate함수는 스티커를 회전(배열 돌리기)을 진행합니다.
- attach함수는 기준 위치를 바탕으로 스티커를 붙일 수 있는지 확인합니다.
결과코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
//스티커 정보 관련 클래스
static class Sticker{
int R, C;
int[][] shape;
public Sticker(int R, int C, int[][] shape){
this.R = R;
this.C = C;
this.shape = shape;
}
}
static boolean[][] visited; //모눈종이 관련 배열
static int result = 0;
static int N, M, K;
//스티커 저장 리스트
static ArrayList<Sticker> stickers = new ArrayList<>();
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
visited = 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());
int[][] sticker = new int[R][C];
for(int j=0;j<R;j++){
st = new StringTokenizer(br.readLine()," ");
for(int s=0;s<C;s++)
sticker[j][s] = Integer.parseInt(st.nextToken());
}
stickers.add(new Sticker(R, C, sticker));
}
//스티커 붙이는 과정 진행
search(0, 0);
bw.write(String.valueOf(result)); //붙인 스티커의 칸수 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
//스티커 붙이는 과정 진행하는 함수
static void search(int cnt, int val){
//모든 스티커 붙이는 과정이 끝났을 때
if(cnt == K){
result = Math.max(val, result);
return;
}
Sticker cur = stickers.get(cnt);
//회전하지 않고 스티커를 붙일 때
for(int i=0;i<N;i++){
for(int j=0;j<M;j++) {
if(cur.R > (N-i) || cur.C > (M-j)) //모눈종이 범위를 벗어날 때
continue;
int temp = attach(i, j, cur); //현재 스티커 붙이기
if(temp == -1) //해당 위치 현재 스티커 붙이기 불가능할 때
continue;
search(cnt+1,val + temp); //다음 스티커 붙이기
return;
}
}
//회전을 통해 스티커 붙이기 진행
for(int i=0;i<3;i++){
rotate(cur); //스티커 회전
for(int j=0;j<N;j++){
for(int s=0;s<M;s++){
if(cur.R > (N-j) || cur.C > (M-s)) //모눈종이 범위를 벗어날 때
continue;
int temp = attach(j, s, cur); //회전한 스티커 붙이기
if(temp == -1) //해당 위치 회전한 스티커 붙이기 불가능할 때
continue;
search(cnt+1,val + temp); //다음 스티커 붙이기
return;
}
}
}
search(cnt+1,val); //현재 스티커 버리고 다음 스티커 붙이기
}
//스티커 회전하는 함수(배열 돌리기)
static void rotate(Sticker sticker){
//배열을 돌린 결과가 저장될 배열
int[][] tempSticker = new int[sticker.C][sticker.R];
//배열 돌리기(90도)
for(int i=0;i<sticker.R;i++){
for(int j=0;j<sticker.C;j++)
tempSticker[j][sticker.R-1-i] = sticker.shape[i][j];
}
//행과 열의 값 반전시키기
int temp = sticker.R;
sticker.R = sticker.C;
sticker.C = temp;
sticker.shape = tempSticker;
}
//스티키 붙이기 진행하는 함수
static int attach(int r, int c, Sticker sticker){
int result = 0;
for(int i=0;i<sticker.R;i++){
for(int j=0;j<sticker.C;j++){
if(sticker.shape[i][j] == 1){
if(visited[r+i][c+j]) //모눈종이에 이미 스티커가 붙인 경우
return -1; //스티커 붙이기 실패
result++;
}
}
}
//스티커 붙인 칸 방문 확인하기
for(int i=0;i<sticker.R;i++){
for(int j=0;j<sticker.C;j++){
if(sticker.shape[i][j] == 1)
visited[r+i][c+j] = true;
}
}
return result; //스티커 붙인 칸 수 반환
}
}'백준' 카테고리의 다른 글
| [백준, Java] 2174번, 로봇 시뮬레이션(시뮬레이션, 구현) (0) | 2023.06.15 |
|---|---|
| [백준, Java] 2170번, 선 긋기 (그리드 알고리즘) (0) | 2023.06.14 |
| [백준, Java] 6593번, 상범 빌딩 알고리즘 분류(그래프 탐색, BFS) (0) | 2023.06.04 |
| [백준, Java] 1926번, 저울 알고리즘 분류(그래프 탐색, BFS) (0) | 2023.06.04 |
| [백준, Java] 2671번, 잠수함식별 알고리즘 분류(문자열) (0) | 2023.06.01 |
댓글