[Python/BOJ] 2314. 이세계 게임

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

2314번: 이세계 게임

문제

트럭 운전사 택희는 오랜 기간 동안의 공로를 인정받아 이세계로 소환되었다. 택희가 소환된 이세계에는 천사 종족 Portableangel과 악마 종족 Legnaelbatrop이 살고 있었다. 택희는 뛰어난 알고리즘 지식을 발휘해 얼마 지나지 않아 두 종족을 모두 지배하는 이세계의 왕이 되었다.

폭군 택희는 지루해지면 이세계의 주민들을 이용해 게임을 한다. 먼저 종족과 무관하게 16명의 개체를 모아서 4×4 격자 형태로 세워 놓는다. 그 다음 각 자리에 어떤 종족이 서야 하는지를 지정해 주고, 그에 맞게 다시 서도록 명령한다. 그러면 이들은 서로 자리를 바꿔서 택희가 원하는 배치를 만들어야 한다. 자리를 바꿀 때는 상하좌우로 인접한 두 개체끼리만 바꿀 수 있으며, 한 개체가 여러 번 자리를 바꿀 수도 있다.

현재 주민들의 배치와 택희가 원하는 배치가 주어질 때, 최소 몇 번의 자리 바꿈이 필요한지 구하여라.

입력

'P' 또는 'L'을 값으로 갖는 4×4 행렬이 공백 없이 주어진다. 이는 현재 주민들의 배치를 나타내며, 'P'는 Portableangel, 'L'은 Legnaelbatrop 종족을 뜻한다.

그 다음 빈 줄이 0개 이상 주어진 뒤 택희가 원하는 배치가 같은 방식으로 주어진다. 택희에게는 최소한의 양심이 있기에 불가능한 배치는 주어지지 않는다.

출력

택희가 원하는 배치를 만들기 위해 필요한 최소 자리 바꿈 횟수를 출력한다.

풀이

Code

import sys
from collections import deque, defaultdict
input = sys.stdin.readline

def solution():
    # 1. 배열 -> 비트 변환 함수 정의
    def array2bit(array):
        # 1-1. 비트 생성
        bit = 0
        # 1-2.
        for i in range(4):
            for j in range(4):
                # 1-2-1. 해당 인덱스 값이 'L'일 경우 비트 삽입
                if array[i][j] == 'L':
                    bit |= (1 << 4 * i + j)
        # 1-3. 비트 반환
        return bit

    # 2. bfs 함수 정의
    def bfs(start):
        # 2-1. 비트 변환 함수 정의
        def check(bit, idx1, idx2, cnt):
            # 2-1-1. 주어진 두 비트 변환
            bit ^= (1 << idx1)
            bit ^= (1 << idx2)
            # 2-1-2. 타겟과 같을 경우 자리 바꿈 횟수 + 1 반환
            if bit == target:
                print(cnt+1)
                exit()
            # 2-1-3. 이외의 경우
            else:
                # 방문하지 않은 경우
                if not visited[bit]:
                    # 방문 처리
                    visited[bit] = True
                    # 큐에 (다음 비트, 자리 바꿈 횟수 + 1) 삽입
                    queue.append((bit, cnt + 1))

        # 2-2. 큐에 (현재 배치 비트, 0) 삽입
        queue = deque()
        queue.append((start, 0))
        # 2-3. 방문 여부 딕셔너리 생성 후 방문 처리
        visited = defaultdict(bool)
        visited[start] = True
        # 2-4.
        while queue:
            # 2-4-1. 큐에서 (현재 배치 비트, 자리 바꿈 횟수) 반환
            now, cnt = queue.popleft()
            # 2-4-2.
            for i in range(4):
                for j in range(4):
                    idx = 4 * i + j
                    # 열변환
                    r = idx + 1
                    # 현재 문자와 오른쪽 문자가 다른 문자일 경우 비트 변환
                    if r < 4 * (i + 1) and (now & (1 << idx) != now & (1 << r)): check(now, idx, r, cnt)
                    # 행 변환
                    d = idx + 4
                    # 현재 문자와 아래쪽 문자가 다른 문자일 경우 비트 변환
                    if d <= 16 and (now & (1 << idx) != now & (1 << d)): check(now, idx, d, cnt)

    now = [list(input().rstrip()) for _ in range(4)]
    target = []
    while True:
        line = input().rstrip()
        if line:
            target.append(list(line))
            target.extend(list(input().rstrip()) for _ in range(3))
            break
    # 3. 현재 배치와 타겟 배치를 비트로 변환
    now = array2bit(now)
    target = array2bit(target)
    # 4. bfs 결과 출력
    print(bfs(now) if now != target else 0)

if __name__ == "__main__":
    solution()