[백준/18808] 스티커 붙이기 (Python)

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

18808번: 스티커 붙이기

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:12:51

 

---

 

문제 설명

 

혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다.

 

 

반면 아래는 올바르지 않은 모눈종이의 예시이다. 첫 번째는 윗쪽에 불필요한 행이 있고, 두 번째는 왼쪽에 불필요한 열이 있다. 그리고 세 번째는 스티커의 각 칸이 상하좌우로 모두 연결되어 있지 않다.

 

 

혜윤이가 스티커를 붙이는 방법은 다음과 같다.

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

 

* 스티커 붙이기의 예시는 원문을 참조해주세요!

 

혜윤이는 스티커를 다 붙인 후의 노트북의 모습이 궁금해졌다. 노트북의 크기와 스티커들이 주어졌을 때 스티커들을 차례대로 붙이고 난 후 노트북에서 몇 개의 칸이 채워졌는지 구해보자

 

 

 

입력 및 출력

 

입력

 

첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 ≤ M ≤ 40), 그리고 스티커의 개수 K(1 ≤ K ≤ 100)이 한 칸의 빈칸을 사이에 두고 주어진다.

그 다음 줄부터는 K개의 스티커들에 대한 정보가 주어진다. 각 스티커는 아래와 같은 형식으로 주어진다.

먼저 i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 Ri(1 ≤ Ri ≤ 10)와 Ci(1 ≤ Ci ≤ 10)가 한 칸의 빈칸을 사이에 두고 주어진다.

다음 Ri개의 줄에는 각 줄마다 모눈종이의 각 행을 나타내는 Ci개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1이다. 0은 스티커가 붙지 않은 칸을, 1은 스티커가 붙은 칸을 의미한다.

문제에서 설명한 것과 같이 스티커는 모두 올바른 모눈종이에 인쇄되어 있다. 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

 

출력

 

첫째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력한다.

 

입력 예시

 

5 4 4
3 3
1 0 1
1 1 1
1 0 1
2 5
1 1 1 1 1
0 0 0 1 0
2 3
1 1 1
1 0 1
3 3
1 0 0
1 1 1
1 0 0

 

출력 예시

 

18

 

 

---

 

풀이

 

전체 지도의 크기 자체가 그렇게 크지 않으므로 한 스티커당 총 탐색 범위 역시 적다. 즉 브루트포스로 모든 경우의 수를 따져 볼 수 있음을 의미한다.

 

스티커가 좌표계 형태로 주어지는데(1이 스티커의 영역), 좌표 리스트로 변환하면 다음과 같은 이점을 얻을 수 있다.

• 전체 지도, 즉 노트북의 특정 위치에 스티커가 붙을 수 있는지 여부를 검토하기 편리하다. 시작 좌표 + 스티커의 상대 좌표가 스티커의 각 부분의 좌표가 되며, 그 각 부분의 좌표가 노트북을 벗어나지 않으며 이미 채워진 칸을 지나지 않는지 여부를 검사하면 된다.
• 회전이 편리하다. 스티커의 좌표를 (x, y)라고 두면, 90도 회전 시 좌표는 (-y, x)가 된다. (행렬의 회전 연산을 생각하면 편하다.) 즉 모든 스티커 좌표를 다음과 같이 변환해 줌으로써 쉽게 회전 연산을 가할 수 있다.

 

이렇게 완성된 스티커 좌표계로 검사를 진행하면 된다.

 

 

 

풀이 코드

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
map_list = [[0]*M for _ in range(N)]
answer = 0

def rotate(sticker) :
  result = list()
  for x, y in sticker :
    result.append((-y, x))
  return result

def patch(sticker) :
  for i in range(N) :
    for j in range(M) :
      cnt = 0
      for x, y in sticker :
        ax, ay = x + j, y + i
        if not (-1 < ax < M and -1 < ay < N and map_list[ay][ax] == 0) :
          break
        cnt += 1
      if cnt == len(sticker) :
        for x, y in sticker :
          ax, ay = x + j, y + i
          map_list[ay][ax] = 1
        return True
  return False

def patch_and_rotate(sticker) :
  global answer
  for _ in range(4) :
    if not patch(sticker) :
      sticker = rotate(sticker)
    else :
      answer += len(sticker)
      return
  return

for _ in range(K) :
  R, C = map(int, input().split())
  sticker_map = [list(map(int, input().split())) for i in range(R)]
  sticker_list = list()
  for i in range(R) :
    for j in range(C) :
      if sticker_map[i][j] == 1 :
        sticker_list.append((j, i))
  patch_and_rotate(sticker_list)

print(answer)

풀이 완료!