백준 문제 풀이 - 폴리오미노 1343번

📜 문제 이해하기

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB
이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

💡 문제 재정의

보드판이 주어졌을 때 폴리오미노로 덮을 수 있는지 확인하기

✏️ 계획 수립

그리디 기법을 활용하면 쉽게 풀 수 있다. 즉 4칸을 덮을 수 있으면 A로 채우고 2칸을 덮을 수 있으면 B로 채운다. 그러다 중간에 .이 끼면 덮을 수 없다고 정의하면 된다. 이 때 now라는 인덱스를 가지고 현재 now 인덱스가 .을 가르키면 다음으로 넘어가는 continue를 활용하면 된다.

💻 계획 수행

if __name__ == '__main__':
    board = input()

    now = 0
    while now < len(board):
        if board[now] == '.':
            now += 1
            continue

        if board[now:now+4] == "XXXX":
            board = "".join((board[:now], "AAAA", board[now+4:]))
            now += 4

        elif board[now:now+2] == "XX":
            board = "".join((board[:now], "BB", board[now+2:]))
            now += 2

        else:
            now = -1
            break

    if now == -1:
        print(-1)
    else:
        print(board)

🤔 회고

그리디 알고리즘으로 풀 수 있는 문제였다. 그리디 알고리즘은 지금 당장 취할 수 있는 가장 좋은 것을 취하는 알고리즘이기에 위와 같은 문제를 풀기에 적합하다.