[Python] 백준 1343 - 폴리오미노

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

1343번: 폴리오미노

문제

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

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

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

입력

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

출력

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

 

폴리오미노란?

---

해결방법 및 코드 설명

AAAA와 BB를 도형이라고 생각하고, x는 AAAA와 BB 블럭을 끼워넣을 수 있는 공간이라고 생각하고 풀이를 했습니다. 어째선지 모양이 같은 도형을 끼워넣는 놀이를 떠올리게 되어 그랬습니다.

 

1. AAAA(이하 A4)와 BB(이하 B2)만을 이용해서 x 자리에 꽂아넣는 것이므로 1, 3, 5, 7, .. 과 같이 x가 홀수개만큼 연달아 있는 경우는 A4와 B2만으로 풀이가 불가능합니다. 따라서 x의 개수가 홀수임을 파악하게 된다면 그 즉시 프로그램을 종료하고 '-1'을 출력하면 될 것이다.

 

2. x 자리에 A4를 끼워넣을지, B2를 끼워넣을지는 x의 개수(이때 xxx 는 3, xxxxxxxx는 8, ...)를 구한다. 개수를 4로 나누고 그 몫만큼 A4를 넣는다. 그리고 나머지를 2로 나눈몫을 B2로 채우면 그만이다. (단, '1'에서 설명했듯 짝수인 경우에만.)

---

지금 드는 고민은 두 가지이다. 하나는 주어진 입력에 대해서 맨 앞부터 뒤까지 전부 읽어가면서 x의 개수를 세고 그 개수만큼 변환 혹은 새 변수에 추가를 해줄 것인지, 다른 하나는 구분점이 '.'이므로 split을 하여 리스트로 문제를 풀 것인지 말이다.

방법1

첫 번째 아이디어를 구현하면 아래와 같다.

입력한 문자열을 가장 앞에서부터 끝까지 훑어가며 'X'인 경우, '.'인 경우를 나눠서 ans에 적절한 값을 추가해준다.

board = input()
leng = len(board)
A4 = "AAAA"; B2 =  "BB"
cnt = 0
ans = ""
chk = True
for i in range(leng+1):
  if i == leng:     # 변환하지 않는 경우를 위해.
      if cnt%2!=0:
        chk = False
      else:
        ans += A4 * (cnt//4) + B2 * ((cnt%4)//2)
      break

  if board[i]=='X': # X 개수 세기
    cnt+=1

  if board[i]=='.':
    if cnt%2!=0:
      chk = False  # 곧장 -1 출력하기.
      break        # 반복문 종료
    
    else:
      ans += A4 * (cnt//4) + B2 * ((cnt%4)//2) + "."
      cnt = 0   # 0으로 초기화

if chk:
  print(ans)
else:
  print(-1)

"# 변환하지 않는 경우를 위해." 에 대한 코드를 굳이 왜 사용했냐면, 반복문을 leng번 까지만 돌리게 되면 XXXX 인 경우 X의 개수만 세고 ans에 결과를 추가해주지 않고 그냥 끝나버리기 때문이다. 따라서 leng+1번 반복해서 XXXX 에서 X의 개수를 보고 A4, B2 중 적절히 추가해주는 것이다.

---

방법2

두 번째 아이디어를 구현할 땐 아래의 코드를 잘 알아두자.

INPUT = "XXXX....XXX.....XX"
INPUT.split('.')
>>> ['XXXX', '', '', '', 'XXX', '', '', '', '', 'XX']

 위 코드는 주어진 입력에 split으로 찢으면 어떤 결과를 반환하는지를 나타내준다. '.'(온점)을 기준으로 split 하기 때문에 '.'이 연달아 있으면 ('.'의 개수-1)만큼 ''이 원소로 존재한다.

 

 

두 번째 아이디어를 구현한 코드는 아래와 같다.

'방법1'과는 달리 문자열을 '.'을 기준으로 split하여 뭉탱이(?)를 만들어 뭉탱이의 길이를 가지고서 ans에 적절한 문자열을 추가해주는 방법이다.

board = input().split('.')
ans = ""
for ele in board:
  leng = len(ele)
  if leng%2!=0:
      ans = '-1.'
      break
  else:
      ans += "AAAA"*(leng//4) + "BB"*((leng%4)//2) + "."
print(ans[:-1])

leng 은 board의 원소인 ele(문자열)의 길이를 의미한다. ele이 ''이라면 leng=0이다. 따라서 '.'이 연달아 입력된 경우(ex: 'XX...XX.....XXXX')에도 오류 없이 잘 처리한다.

 

그리고 정답을 출력할 때 ans[:-1]로 인덱싱을 하는 이유는 마지막 반복에서 필요없는 '.'을 달아주기 때문에 그렇다.

 

---

 

두 코드에 대한 결과는 아래와 같다.

코드길이가 596인 제출이 방법1이고, 198인 제출이 방법2이다.

코드의 길이도 길이이고, 가독성도 방법2가 더 뛰어난 것 같다. 맨 처음엔 방법1이 더 좋을 것이라고 생각하였는데, 모두 다 하고 보니 방법2가 오히려 더 좋은 방법인 것 같아서 놀랍다.