문제
혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.
아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다.
반면 아래는 올바르지 않은 모눈종이의 예시이다. 첫 번째는 윗쪽에 불필요한 행이 있고, 두 번째는 왼쪽에 불필요한 열이 있다. 그리고 세 번째는 스티커의 각 칸이 상하좌우로 모두 연결되어 있지 않다.
혜윤이는 자신의 노트북에 이 스티커들을 붙이기로 했다. 혜윤이의 노트북은 마침 직사각형 모양이고, 스티커가 인쇄된 모눈종이와 같은 간격으로 격자가 그려져 있다. 혜윤이는 스티커들을 먼저 받았던 것부터 차례대로 격자에 맞춰서 붙이려고 한다.
혜윤이가 스티커를 붙이는 방법은 다음과 같다.
스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
아래의 예시를 통해 스티커를 붙이는 과정을 이해해보자. 노트북은 세로 5칸, 가로 4칸 크기이고, 혜윤이가 가지고 있는 스티커들은 아래와 같다. 왼쪽에서 오른쪽 순으로 스티커를 붙일 것이다.
첫 번째 스티커는 회전 없이 온전히 붙일 수 있는 공간이 아래와 같이 6곳이 있다.
이 중에서 가장 위쪽의 위치, 가능한 가장 위쪽의 위치가 여러 개이면 그 중에서 가장 왼쪽의 위치는 첫 번째이다. 스티커를 붙인 후 노트북의 모양은 아래와 같다.
두 번째 스티커는 회전 없이 온전히 붙일 수 있는 공간이 없다. 그러나 시계 방향으로 90도 회전한 후에는 붙일 수 있는 공간이 1개 생긴다. 해당 공간에 스티커를 붙인 후 노트북의 모양은 아래와 같다.
세 번째 스티커는 스티커를 시계방향으로 0, 90, 180, 270도 회전시킨 모양에 대해 전부 확인을 해도 스티커를 붙일 수 있는 공간이 없다. 그러므로 해당 스티커를 붙이지 않고 버린다.
네 번째 스티커는 스티커를 시계방향으로 0, 90, 180도 회전 시킨 모양에 대해 온전히 붙일 수 있는 공간이 없다. 그러나 시계 방향으로 270도 회전한 후에는 공간이 1개 생긴다. 스티커를 붙인 후 노트북의 모양은 아래와 같다. 최종적으로 노트북의 18칸이 스티커로 채워졌다.
혜윤이는 스티커를 다 붙인 후의 노트북의 모습이 궁금해졌다. 노트북의 크기와 스티커들이 주어졌을 때 스티커들을 차례대로 붙이고 난 후 노트북에서 몇 개의 칸이 채워졌는지 구해보자.
풀이
두가지 문제를 해결해야 한다.
- 스티커를 붙일 수 있는지 여부를 확인하고 붙이는 것
- 스티커를 90도로 회전시키는 것
1번인 붙일 수 있는지 여부를 확인하는 것은 기존에 주어진 row의 최대 길이인 N에서 스티커의 row 길이를 빼주고 1을 더해주면 row에서 몇번 시도할 수 있는지가 나오고 column의 경우도 마찬가지이다.
can_paste 함수를 통해서 붙일 수 있는지 여부를 검사하고 paste_a_sticker 함수로 노트북리스트 값을 변경해주었다.
이 과정에서 for문 탈출 구문이 조금 까다로웠는데 is_paste라는 불리언값을 통해서 for문을 break할지 말지를 결정했다. (사실 이 for문 탈출을 못해서 함수와 로직을 다 짰으나 구현해내지는 못했다. 시뮬레이션에서는 이런 테크닉이 성패를 가르는 중요한 요소라고 생각한다.)
2번 90도회전은 90도 180도 270도 회전은 결국 현재 스티커에서 90도 이동시키고 그 리스트를 다시 90도 이동 시키는 반복이기 때문에 90도 회전함수 하나만 있으면 충분하다.
row와 col의 값이 바뀌어서 값이 들어갈 예정이니까 둘을 반대로 가지는 rotated_matrix값을 미리 설정해두고 거기에 처음에는 값이 반대로 바뀌기만 하면 90도 회전이 되겠지 하는 나이브한 생각으로 구현을 했으나 이렇게 구현을 하면 90도 회전 후 좌우가 반전된 값이 나오게 된다.
수학적으로 이게 맞는지는 모르겠지만 x축을 기점으로 반전시켜야 하는데 y축 반전도 같이 시킨 것 같아서 column값을 어떻게 뒤집을지 생각해보니 주어진 스티커의 행의 길이가 3이라고 하고 현재 순회하고 있는 row의 인덱스가 0이라면 0, 1, 2에서 2로 보내고 1은 그대로 2는 0으로 보내면 될거라고 생각을 해서
3 - 1 - 0 → 2
3 - 1 - 2 → 0
스티커의 row - 1 - 순회중인 row 인덱스라는 규칙을 찾아내서 rotate_90_degree함수를 만들 수 있었다.
def rotate_90_degree(cur_row : int, cur_col : int , sticker:list[list[int]]):
rotated_matrix = [[0] * cur_row for _ in range(cur_col)]
for r in range(cur_row):
for c in range(cur_col):
rotated_matrix[c][cur_row-1-r] = sticker[r][c]
return rotated_matrix
def can_paste(row:int, col:int):
for r in range(row):
for c in range(col):
if note_book[i+r][j+c] == 1 and sticker[r][c] == 1:
return False
return True
def paste_a_sticker(row, col):
for r in range(row):
for c in range(col):
if sticker[r][c] == 1:
note_book[i+r][j+c] =1
if __name__ == "__main__":
N, M, K = map(int, input().split())
note_book = [[0] * M for _ in range(N)]
for _ in range(K):
row, col = map(int, input().split())
sticker = [list(map(int, input().split())) for _ in range(row)]
for _ in range(4):
sticker_row = len(sticker)
sticker_col = len(sticker[0])
is_paste = False
for i in range(N - sticker_row+1):
if is_paste: break
for j in range(M - sticker_col+1):
if can_paste(sticker_row, sticker_col):
paste_a_sticker(sticker_row, sticker_col)
is_paste = True
break
if is_paste: break
sticker = rotate_90_degree(sticker_row, sticker_col, sticker)
print(N * M - sum(map(lambda x: x.count(0), note_book)))피드백
실제로 코딩테크닉을 늘리기에는 시뮬레이션 문제가 제일 좋을 것 같다는 생각이 든다.
다른 알고리즘 문제들은 사고력을 묻는다면 (구현이 사고력이 필요없다는 얘기는 아니지만) 이 문제 유형은 실제로 내가 머리속으로 생각한 것들을 코드로 만들어낼 수 있는지 묻는다.
오늘 문제도 for문 탈출을 불리언값으로 할 수 있다는 걸 알면서도 막상 for문에 적용시키려고 하니까 손이 멈추게 되는걸 느꼈다.
강의를 다 듣고 나면 하나씩 사이클을 돌면서 현재 레벨도 파악하고 레벨을 어떻게 상승시킬지를 고민하면서 알고리즘 문제를 풀어봐야겠다.
