백준 1343: 폴리오미노 (python)

문제

---

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

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

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

입력

---

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

출력

---

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

풀이

입출력 예제:
XXXX.XX → AAAA.BB
XXXXXX.XX → AAAABB.BB
XXX.XXXX → -1
XXXXXXXXXX.XX → AAAAAAAABB.BB
XX...XXXX → BB...AAAA

폴리오미노는 같은 모양의 정사각형을 여러 개 이어붙인 모양을 말한다고 한다.
두 개 이어붙이면 도미노, 세 개 이어붙이면 트리오미노... 라고 한다.
이 문제는 테트로미노(AAAA)와 도미노 (BB)로 주어진 보드를 채우도록 하는 문제다.
칠교놀이... 같은 느낌

X를 채울 수 있는 조건
1. X가 4의 배수 개 연속해 있을 때
2. X가 2의 배수 개 연속해 있을 때

이 문제는 return을 쓰고 싶어서 함수를 정의해서 썼다.

def solution():
  board = list(input()) # 이렇게 받으면 인풋이 ['X','X','.','X','X']와 같이 들어온다.
  last_index = -1 
  answer = ''
  
  for i in range(len(board)):
    if (board[i] == '.'):
      if (i-last_index) % 4 == 1:
        answer += 'A' * (i-last_index-1) 
        answer += '.'
        last_index = i
      elif (i-last_index) % 2 == 1:
        answer += 'AAAA' * int((i-last_index) // 4)
        answer += 'BB' * int(((i-last_index) % 4) // 2)
        answer += '.'
        last_index = i
      else: 
        print(-1)
        return 0
  last = len(board) - 1      
  if (last -last_index) % 4 == 0:
    answer += 'A' * (last-last_index) 
  elif (last-last_index) % 2 == 0:
    answer += 'AAAA' * int((last-last_index) // 4)
    answer += 'BB' * int(((last-last_index) % 4) // 2)
  else: 
    print(-1)
    return 0
  
  print(answer)

solution()

for문에서는 '.'과 '.' 사이의 거리로 X를 채울지 말지 판단한다.
'.'이 여러 번 등장해도 같은 로직을 적용하기 위해서, last_index를 -1로 초기화했다.
부연 설명: last_index = 0이면, 첫 번째 '.'이 나타났을 때와, 그 이후의 로직이 달라져야 한다.

마지막 '.'으로부터 배열 끝까지의 보드는'.'과 '.' 사이의 거리로만 판단할 수 없는 케이스다.
for문을 다 돌고 나서 따로 검사하도록 했다.

두 번의 조건 확인 (for문과 last) 중, X를 채울 수 없는 조건이 등장하는 경우 -1을 출력하고 return 0로 함수를 종료하도록 했다.

• 다 쓰고 보니: 그냥 return -1, return answer 하고 print(solution()) 하면 되는데... 약간 바보같이 쓴 듯

다른 풀이 (구글링)

---

1. 배열로 입력받고, 순회하며 X의 개수를 센다. (4의 배수 또는 2의 배수가 될 때마다 변환 & .을 만났을 때 return 또는 continue 결정)

2. 문자열로 입력받고, (1) XXXX를 AAAA로 replace, (2) XX를 BB로 replace (3) X의 개수를 세서 !=0이면 return -1
   - 이거 천재같네...

   def solution():
   board = input()
   board = board.replace('XXXX', 'AAAA')
   board = board.replace('XX', 'BB')
   
   if (board.count('X') != 0):
   return -1
   return board
   print(solution())

   replace는 새로운 값을 반환한다. 반환값을 받아줄 자리를 꼭 정해줘야 한다.
   replace 쓰다가 똑같은 실수 또 해서 적어둠.