[백준] 18808 스티커 붙이기

1. 문제

 

2. 접근방법

문제가 저어어어어엉말 길다

문제가 긴 만큼 설명도 아주 자세히 되어있어 그냥 시키는 데로만 구현 해내면 별 무리없이 풀 수 있는 문제

 

다만 구현할 기능이 많아서 차근차근 꼬이지 않게 잘 구현 해야겠다.

 

기능들만 나열하면

1. 스티커가 들어갈 수 있는 모든 점(0 ~ 노트북 크기 - 스티커 크기 + 1 ) 중 하나씩 선택해서

2. 노트북에 이미 붙여져 있는 스티커와 겹치는지 검사하고

3. 겹치는 부분이 있으면 1번으로 가서 다른 점 선택

4. 겹치는 부분이 없으면 노트북에 붙이고 다음 스티커로

5. 모든 점에 대해 검사 했는데 붙일 곳이 없다면 90도 회전

6. 다시 1번 부터 붙여지는 곳 찾을 때까지 반복

7. 끝까지 못찾으면 그냥 스티커 버리고 다음 스티커로

 

8. 다 붙이고 노트북에 붙여진 총 칸수 출력

 

정말 많다 ;;

복잡한 만큼 나는 구현할 때 기능 별로 함수를 만들어서 꼬이지 않게 하였다.

3. 풀이

1.맵 크기 (N,M) 에 맞게 생성

2. 스티커 하나 입력 받자마자 노트북에 붙이러 가기

3. (0,0) 부터 (N - sticker.length +1 , M - sticker[0].length +1)까지 돌며

4. 해당 점에 붙일 수 있는지 (map에 이미 붙여진 1과 스티커가 들어가고 싶어하는 1들이 겹치지 않는지) 검사

5 - 1. 붙일 곳이 있다면 맵에 스티커 붙이고 2번으로 이동 (스티커를 붙일 때 1의 갯수 count)

5 - 2. 붙일 수 있는 곳이 없다면 스티커를 90도 회전 후 3번으로 이동

6. 모든 스티커를 붙이면 count 출력

 

4. 자바 코드

package 백준;

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

public class P18808스티커붙이기 {
	static int map[][], N, M, K, result;

	static boolean attach(int[][] sticker) {
		for (int i = 0; i < N - sticker.length + 1; i++) // 들어갈 수 있는 모든 점에 대해 검사하기
			for (int j = 0; j < M - sticker[0].length + 1; j++)
				if (check(sticker, i, j)) { // 모든 점중 한점에 대해 검사
					attachOne(sticker, i, j);
					return true;
				}

		return false;
	}

	static boolean check(int[][] sticker, int row, int col) { // 한점에 대해 겹치는 위치 없는지 확인
		for (int i = 0; i < sticker.length; i++)
			for (int j = 0; j < sticker[0].length; j++)
				if (sticker[i][j] == 1 && map[row + i][col + j] == 1)
					return false;
		return true;
	}

	static void attachOne(int[][] sticker, int row, int col) { // 조건에 부합하면 맵에 붙이기

		for (int i = 0; i < sticker.length; i++)
			for (int j = 0; j < sticker[0].length; j++)
				if (sticker[i][j] == 1) { // 붙이는게 스티커 부분이면 result +1
					map[row + i][col + j] = sticker[i][j];
					result++;
				}
	}

	static int[][] turn(int[][] sticker) { // 90도 회전
		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;
	}

	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 int[N][M];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int strow = Integer.parseInt(st.nextToken());
			int stcol = Integer.parseInt(st.nextToken());
			int[][] sticker = new int[strow][stcol];
			for (int j = 0; j < strow; j++) {
				st = new StringTokenizer(br.readLine());
				for (int k = 0; k < stcol; k++) {
					sticker[j][k] = Integer.parseInt(st.nextToken());
				}
			}
			for (int tu = 0; tu < 4; tu++) {
				if (attach(sticker)) //붙여 졌으면 종료
					break;
				sticker = turn(sticker); //안붙여졌으면 90도 돌려서 다시
			}
		}
		System.out.println(result);
	}

}

5. 마치며

 

백준 자바 중에 8등한거 자랑~~

 

 

https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기