[Python/파이썬] 백준 1343번 폴리오미노

1343번: 폴리오미노

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

코드

board = input()

def polyomino(cnt):
    if cnt % 2 == 1:    # 덮을 수 없는 경우(홀수인 경우)
        print(-1)
        exit()
    if cnt == 0:
        return ''
    tmp = ''
    a = cnt // 4
    b = (cnt - a * 4) // 2
    for _ in range(a):
        tmp += 'AAAA'
    for _ in range(b):
        tmp += 'BB'
    return tmp

cnt = 0
ans = ''
for b in board:
    if b == '.':
        ans += polyomino(cnt)
        ans += '.'
        cnt = 0 
    else:
        cnt += 1
if cnt != 0:
    ans += polyomino(cnt)
print(ans)

board 변수에 보드판 문자열을 입력받는다.

board 문자열에 대해 반복문을 돌면서 'X'가 나오면 cnt를 1 증가시키고 '.'이 나오면 ans 문자열에 polyomino(cnt) 함수의 리턴값을 더해줄 것이다. 여기서 polyomino() 함수는 다음과 같이 동작한다.

1. 우리가 쓸 수 있는 폴리오미노는 4개짜리, 2개짜리가 있다. 따라서 덮어야하는 면적의 크기가 홀수이면 덮을 수 없으므로 -1을 출력하고 프로그램을 종료한다.
2. cnt가 0이면 '.'이 연달아 나온 경우이므로 빈 문자열을 리턴한다.
3. 우리는 사전 순으로 가장 앞서는 답을 출력해야 하므로 "AAAA" 폴리오미노를 최대한 많이, 그리고 "BB" 폴리오미노보다 먼저 사용하여야 한다. 그러므로 "AAAA" 폴리오미노의 개수를 저장할 a 변수에 cnt의 값을 4로 나눈 몫을 저장하고 "BB" 폴리오미노의 개수를 저장할 b 변수에 cnt에서 "AAAA" 폴리오미노가 차지하는 칸 수(a * 4)를 뺀 값을 2로 나눈 몫을 저장해준다. 그리고 tmp 문자열에 "AAAA", "BB" 폴리오미노 순서로 앞에서 구한 개수만큼 담아서 리턴한다.

이렇게 polyomino(cnt)의 리턴값을 ans 문자열에 더해주고 '.' 또한 ans에 더해준다. 그리고 cnt는 0으로 초기화한다.

board 배열에 대해 반복문을 다 돌면 cnt를 확인해서 0이 아니라면 board 문자열의 마지막이 'X'여서 아직 마지막 폴리오미노로 덮어주어야 할 부분이 처리가 되지 않은 것이니 ans에 polyomino(cnt) 값을 더해주어야 한다.