[백준] 18808 스티커 붙이기

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

18808번: 스티커 붙이기

 

풀이

스티커가 들어갈 수 있는지 체크하고 들어가지 못하면 90도 회전시킨 후 다시 확인하는 단순한 구현이지만 세세한 부분을 체크해야하는 문제였다.

 

ROW, COL, K = map(int, input().split())
board = [[0 for _ in range(COL)] for _ in range(ROW)]
stickers = []

for i in range(K):
    r, c = map(int, input().split())
    temp = [list(map(int, input().split())) for _ in range(r)]
    stickers.append(temp)

먼저 가로, 세로, 스티커의 갯수를 입력받고 전체 board를 설정한다.
그리고 K개의 스티커를 입력 받아 stickers 리스트에 저장하였다.

 

def check_sticker(sticker, y, x):
    r, c = len(sticker), len(sticker[0])

    for i in range(r):
        for j in range(c):
            if sticker[i][j] == 1 and board[y + i][x + j] == 1:
                return False

    for i in range(r):
        for j in range(c):
            if sticker[i][j] == 1:
                board[y + i][x + j] = 1
    return True

스티커가 들어갈 수 있는지 체크하는 함수이다.
board가 1일때 스티커도 1이면 붙일 수 없기 때문에 False를 반환하고 아닌 경우에는 다시 반복을 하면서
board에 스티커를 붙였다는 의미로 1을 넣어줬다.

특정 좌표부터 스티커의 크기까지 체크하기 때문에 입력 값으로 y, x를 받아야한다.

 

def rotate_sticker(sticker):
    c, r = len(sticker), len(sticker[0])

    temp = [[0 for _ in range(c)] for _ in range(r)]
    for i in range(r):
        for j in range(c):
            temp[i][j] = sticker[c-1-j][i]

    return temp

스티커를 붙일 수 없는 경우에 스티커를 90도 회전시키는 함수이다. 여기서 중요한 것이
일반적인 N, N배열의 회전의 경우 row, col의 크기가 변하지 않기 때문에 문제가 없지만
이 경우에는 R -> C, C -> R로 변하기 때문에 해당 부분을 잘 고려해야한다.

 

for sticker in stickers:
    turn = 1
    while True:
        flag = False
        r, c = len(sticker), len(sticker[0])
        for y in range(ROW - (r - 1)):
            for x in range(COL - (c - 1)):
                if check_sticker(sticker, y, x) is True:
                    flag = True
                    break
            if flag:
                break

        if flag is False:
            if turn == 0:
                break
            sticker = rotate_sticker(sticker)
            turn = (turn + 1) % 4
        elif flag:
            break

위의 2가지 함수를 이용하여 스티커를 붙이고 같은 스티커가 2개 붙으면 안되기 때문에
스티커가 붙은 경우에는 break를 해주었다.

스티커를 3번까지 회전시키기 때문에 turn을 설정해서 4번 돌았을 경우 break하는 형식으로 구현했는데
그냥 for문을 4번 반복시키는 것이 더 좋은 방법인 것 같다.

 

answer = 0
for i in range(ROW):
    for j in range(COL):
        if board[i][j] == 1:
            answer += 1

print(answer)

마지막에 전체 배열을 탐색하면서 스티커가 붙은 공간의 갯수를 세아리면 된다.

 

전체 코드

ROW, COL, K = map(int, input().split())
board = [[0 for _ in range(COL)] for _ in range(ROW)]
stickers = []

for i in range(K):
    r, c = map(int, input().split())
    temp = [list(map(int, input().split())) for _ in range(r)]
    stickers.append(temp)

def rotate_sticker(sticker):
    c, r = len(sticker), len(sticker[0])

    temp = [[0 for _ in range(c)] for _ in range(r)]
    for i in range(r):
        for j in range(c):
            temp[i][j] = sticker[c-1-j][i]

    return temp

def check_sticker(sticker, y, x):
    r, c = len(sticker), len(sticker[0])

    for i in range(r):
        for j in range(c):
            if sticker[i][j] == 1 and board[y + i][x + j] == 1:
                return False

    for i in range(r):
        for j in range(c):
            if sticker[i][j] == 1:
                board[y + i][x + j] = 1
    return True

for sticker in stickers:
    turn = 1
    while True:
        flag = False
        r, c = len(sticker), len(sticker[0])
        for y in range(ROW - (r - 1)):
            for x in range(COL - (c - 1)):
                if check_sticker(sticker, y, x) is True:
                    flag = True
                    break
            if flag:
                break

        if flag is False:
            if turn == 0:
                break
            sticker = rotate_sticker(sticker)
            turn = (turn + 1) % 4
        elif flag:
            break
answer = 0
for i in range(ROW):
    for j in range(COL):
        if board[i][j] == 1:
            answer += 1

print(answer)

스티커를 4번 회전시켰을 때 정지하는 부분이 조금 깔끔하지 못하게 구현되어 있는 것 같다.

이 문제의 경우 최대한 많은 스티커를 붙이는 것이 아니라 1번째 스티커부터 붙일 수 있는 첫번째 위치에 붙이기 때문에 단순 구현으로 해결할 수 있어서 복잡한 문제는 아니였지만 NxN의 배열이 아닌 경우는 ROW -> COL, COL -> ROW로 결과 배열의 크기가 변한다는 점을 신경써야하는 문제였다.