[백준 1343번] 폴리오미노

문제 링크 >> https://www.acmicpc.net/problem/1343

 

 

📋 문제

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

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

이때, '.'는 폴리오미노로 덮으면 안 된다.

 

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

 

 

👉 입력

첫째 줄에 보드판이 주어진다.

보드판의 크기는 최대 50이다.

 

 

👈출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다.

만약 덮을 수 없으면 -1을 출력한다.

 

 

📝 풀이

board = input()
arr = board.split('.')

def poly(arr):
  string = ""
  for item in arr:
    if len(item) % 2 != 0:
      return -1
    
    numA = len(item) // 4
    numB = len(item) % 4
    string += 'AAAA' * numA + 'BB'*(numB-1) + '.'
    
  return string[:-1]

if __name__ == "__main__":
  print(poly(arr))

 

폴리오미노로 덮는 것이 불가능한 경우 바로 -1을 리턴하기 위해 함수로 구현했다.

'.'은 폴리오미노로 덮으면 안되기 때문에 board를 '.'을 기준으로 split하고 이들을 arr에 저장했다.

 

poly 함수에서는 먼저 정답을 담을 빈 문자열 string을 선언한다.

이후 for문에서 arr의 요소들을 하나씩 살펴본다.

 

폴리오미노가 AAAA와 BB로 주어졌기 때문에 item의 길이가 홀수일 경우에는 폴리오미노로 덮는 것이 불가능하다.

이 경우 바로 -1을 리턴해준다.

 

위 조건에 걸리지 않았다면 폴리오미노로 덮는 것이 가능하다.

사전순으로 가장 앞서는 답을 출력하기 위해서는 AAAA의 등장 횟수가 BB보다 많아야 한다.

AAAA를 더 많이 채우기 위해서는 AAAA부터 채우고 나머지 빈 공간을 BB로 채우면 된다.

따라서 AAAA는 item의 길이에서 4를 나눈 몫으로 채우고 나머지 공간이 존재할 경우 BB를 넣는다.

이때 split 과정에서 없어진 '.'도 같이 더해준다.