백준 1473 미로탈출 파이썬

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

1473번: 미로 탈출

 

 

 

일단 스위치를 켜고 끄면 비트마스킹을 떠올리는 것이 가장 빠르다. 비트마스킹이 가능한지를 먼저 검토해봐야한다.

​

1. 입력으로 들어올 수 있는 최대 크기는 49다.
2. 각 행, 열은 총 7개씩 들어올 수 있다. 행, 열의 비트 상태를 나타낼 수 있는 배열은 각각 128(2^7)개다. 각 행마다 각 열의 비트 상태가 나열될 수 있으니 128 * 128이된다.
3. 총 만들어지는 열은 128 * 128 * 49 * 2(2 = 방문 처리, 실제 맵 상태 2가지 )160만개다.

​

메모리 계산을 해보면 6MB 정도로 확인된다. 160만개를 V+E로 방문하게 되면 큰 무리 없이 된다. 따라서 비트마스크 + BFS로 처리할 수 있다.

​

​개인적으로 가장 어려웠던 부분은 비트마스킹 맵을 만드는 것이었다. 처음에는 멍청한 생각으로 각 셀마다 4개의 상태가 있으니 그렇게 만들어볼까? 했는데... 기껏 만들어놓고 보니 이렇게 하면 모든 경우의 수를 체크할 수 없다는 것을 알 수 있게 되었다. 따라서 새로 생각해서 위와 같이 풀었다.

​

정리하면...

​​

1. 비트마스킹을 위해 n,m에 대해 비트마스킹을 처리할 수 있는 방문배열 + 실제 맵상태 배열을 만든다.
2. 실제 맵 상태 배열을 만든 후, 어떤 비트가 켜져있는지를 확인해서 실제로 그 맵을 Rotate 시켜주는 역할을 한다.
3. 필요한 맵을 만든 후 BFS를 돌린다.

 

import sys
from collections import deque


# Solution 함수
def bfs(v, my_map) :

    # 초기화
    que = deque()
    que.append((0,0,0,0,0))

    #방문 처리
    v[0][0][0][0] = 0

    while que :

        #rbit : 현재 row bit
        #cbit : 현재 column bit
        #time : 현재 방문 시간

        r, c, rbit, cbit, time = que.popleft()
        next_time = time + 1

        #이 자리에서 스위치를 껐을 때, 비트 상태 전환 (XOR 비트 연산 처리)
        next_rbit = rbit ^ (1 << r)
        next_cbit = cbit ^ (1 << c)

        #도착했으면 종료
        if r == n-1 and c == m-1 :
            print(time)
            return


        # 이 자리에서 스위치를 켤 때
        if v[next_rbit][next_cbit][r][c] > next_time :
            v[next_rbit][next_cbit][r][c] = next_time
            que.append((r,c, next_rbit, next_cbit, next_time))

        # 좌우 이동 확인
        for rr, cc in tra_list_lr:
            next_r, next_c = r + rr, c + cc
            if -1 < next_r < n and -1 < next_c < m :

                # Validation
                if ((my_map[rbit][cbit][r][c] == "D" or my_map[rbit][cbit][r][c] == "A") and
                    (my_map[rbit][cbit][next_r][next_c] == "D" or my_map[rbit][cbit][next_r][next_c] == "A")
                    and v[rbit][cbit][next_r][next_c] > next_time) :

                    que.append((next_r, next_c, rbit, cbit, next_time))
                    v[rbit][cbit][next_r][next_c] = next_time

        # 위아래 이동 확인
        for rr, cc in tra_list_ud:
            next_r, next_c = r + rr, c + cc
            if -1 < next_r < n and -1 < next_c < m :

                # Validation
                if ((my_map[rbit][cbit][r][c] == "C" or my_map[rbit][cbit][r][c] == "A") and
                        (my_map[rbit][cbit][next_r][next_c] == "C" or my_map[rbit][cbit][next_r][next_c] == "A")
                        and v[rbit][cbit][next_r][next_c] > next_time):
                    que.append((next_r, next_c, rbit, cbit, next_time))
                    v[rbit][cbit][next_r][next_c] = next_time


    # 만약에 이동 못할 때, 그만두기.
    print(-1)

# 그래프 회전 함수

def rotate_Row(my_list, rbit_list):
    global n, m

    for r in rbit_list:
        for c in range(m):
            if my_list[r][c] == "C":
                my_list[r][c] = "D"
            elif my_list[r][c] == "D":
                my_list[r][c] = "C"


def rotate_Col(my_list, cbit_list):
    global n, m

    for c in cbit_list:
        for r in range(n):
            if my_list[r][c] == "C":
                my_list[r][c] = "D"
            elif my_list[r][c] == "D":
                my_list[r][c] = "C"



#그래프 복사용 함수
def copy_array(my_list) :
    global n,m
    return_list = [[] for _ in range(n)]
    for idx,value in enumerate(my_list) :
        for k in value :
            return_list[idx].append(k)

    return return_list


# 좌우 이동 그래프
tra_list_lr = [[0, 1], [0, -1]]

# 상하 이동 그래프
tra_list_ud = [[1, 0], [-1, 0]]



# 값 입력
n,m = map(int,sys.stdin.readline().split())
my_list = [[] for _ in range(n)]
for i in range(n):
    temp = sys.stdin.readline().rstrip()
    for k in temp :
        my_list[i].append(k)

#비트 샹태에 따른 방문 배열 : [Row 비트 상태][Col 비트 상태][Row][Col]
v_map = [[[[1000 for _ in range(m)] for _ in range(n)] for _ in range(2**m)] for _ in range(2**n)]

#비트 샹태에 따른 실제 맵 상태 : [Row 비트 상태][Col 비트 상태][Row][Col]
my_map = [[copy_array(my_list) for _ in range(2**m)] for _ in range(2**n)]


# my_map에서 비트 상태에 따라 어떤 맵을 가지고 있는지 만들어준다.
for rbit in range(2**n):
    rbit_list = []

    # Row에 돌려야할 비트 있는지 확인
    for i in range(n):
        if rbit & (1 << i) != 0 :
            rbit_list.append(i)

    for cbit in range(2**m) :
        cbit_list = []

        # Col에 돌려야할 비트 있는지 확인
        for k in range(m) :
            if cbit & (1 << k) != 0 :
                cbit_list.append(k)

        # 비트 정보 넘겨서 Rotate
        rotate_Row(my_map[rbit][cbit], rbit_list)
        rotate_Col(my_map[rbit][cbit], cbit_list)



#문제 풀이
bfs(v_map, my_map)