[BAEKJOON/Python3] 백준 1343 폴리오미노

www.acmicpc.net/problem/1343

1343번: 폴리오미노

＊링크로 접속하여 문제를 확인할 수 있습니다.

 

AAAA와 BB 형태의 폴리오미노를 무한개 가지고 있을 때 폴리오미노를 이용하여 '.'와 'X'로 이루어진 보드판을 모두 덮을 수 있는지를 찾아야 합니다. 'X'는 겹침없이 덮어야하며 '.'는 덮으면 안되는 부분입니다. 사전순으로 가장 앞서는 답을 출력해야 하며 모두 덮을 수 없다면 -1을 출력합니다.

여러가지 방법이 있을 수 있겠지만 저는 X들을 B로 먼저 바꾼 후 B가 연속해서 4개가 있다면 A로 바꾸도록 해서 문제를 해결했습니다.

 

코드

B로 먼저 모두 바꾼 뒤 replace를 이용해서 A로 바꾸는 방법

 

먼저 보드판을 입력 받고, poly라는 변수에는 최종 정답을 저장할 것이며 count 변수를 이용해서 연속하는 X의 개수를 셀 것 입니다. 이 때 count는 최대 2로 하여 X를 B로 바꾸는데에만 집중하도록 했습니다. count가 2가 되면 poly에는 BB를 추가하고 count는 0으로 초기화했으며 i가 '.'인 경우에는 count가 1이라면 모두 덮는 것이 불가능한 상황이므로 반복문을 종료하였고 반복문 밖에서는 정답을 찾을 수 없다는 의미에서 poly 값을 -1로 바꾸었습니다. i일 때 count는 0 또는 1인 경우밖에 없기 때문에 1이 아닌 경우에는 poly에 '.'을 추가하였습니다. (정답에 '.'도 포함되기 때문)

이렇게 구하면 모든 X를 폴리오미노 BB로 덮은 것인데 여기서 BBBB 처럼 연속으로 BB가 두 개 놓인 경우에는 AAAA로 바꿀 수 있도록 replace를 이용했습니다.

 

replace를 이용하지 않고 처음에 B뿐만 아니라 A도 함께 바꾸는 방법으로 다시 해보았습니다.

 

코드

처음부터 A와 B로 모두 바꾸는 방법

 

대부분의 방법은 동일하지만 count가 최대 4까지 갈 수 있다는 차이점이 존재합니다. 따라서 홀수개를 따질 때 count가 1인 것 뿐만 아니라 3인 것도 따져줘야 합니다. 그래서 나머지를 이용하여 홀수를 분리하였다는 것을 알 수 있습니다. count가 2일 때는 동일하게 BB를 추가하지만 count를 0으로 초기화하지 않고 계속 진행하여 count가 4가 된다면 아까 넣었던 BB를 제외하고 AAAA를 추가하면서 count를 0으로 초기화한 것 입니다. 이렇게 할 경우에는 i가 '.'일 때 count가 0,1,2,3이 될 수 있기 때문에 count를 0으로 바꾸는 작업이 필요합니다.

 

replace를 이용하면 해결될 듯하여 처음에는 B만 바꾸는데 집중하고 해결하였으나 해결한 후, 이 방법으로 처음부터 정답을 구할 수는 없을까 하며 추가하여 밑에 코드를 완성하였습니다.