ABC 332 D번 복기 - 행,열 바꿔서 다른 2차원 배열과 똑같이 만드는법(BFS가 된다고?)

1. 문제

 

D - Swapping Puzzle (atcoder.jp)

D - Swapping Puzzle

 

2. 풀이

 

비슷한 문제들이 그리디로 풀려가지고... 숫자 다르면 무조건 바꾸는 그리디인가도 생각해봤는데..

 

제한이 H,W가 5 이하라서 완전탐색이 가능할 것 같다고 생각을하고,

 

생각까진 하더라도 완전탐색을 어떻게 해야할지..

 

근데 그 전에 문제부터 제대로 못읽었던것도 문제..

 

• Choose an integer i satisfying 1≤i≤H−1 and swap the i-th and (i+1)-th rows in grid A.
• Choose an integer i satisfying 1≤i≤W−1 and swap the i-th and (i+1)-th columns in grid A.

 

i번째랑 j번째를 바꾸는게 아니라 i를 정하면, i번째랑 i+1번째를 바꾸는거더라고..

 

그러면 이제 완전탐색을 행에 대한 인덱스 5! * 열에 대한 인덱스 5! = 14400가지를 생성해서 바꿔보면 될려나

 

근데 행만 바꿔보는것도 있고.. 열만 바꿔보는것도 있고.. 단순하게 생각하면 구현하기 쉽지않을것 같다

 

해법을 보니 BFS로 가능하다고 하더라고..

 

이게 BFS가 된다고?

 

A라는 배열 자체를 하나의 상태로 두고 A에서 행 바꿔보고 방문하지 않은 것이라면 큐에 넣고

 

열 바꿔보고 방문하지 않은 것이라면 큐에 넣고..

 

다시 큐에서 꺼낼때, 행끼리만 바꾼 배열은 열도 서로 바꿔보고

 

열끼리만 바꾼 배열은 행도 서로 바꿔보니, 모든 행,열을 서로 바꿔보는 완전탐색이 된다

 

근데 방문상태는 어떻게 체크해??

 

그냥 딕셔너리에 행이나 열을 바꾼 배열 A 자체를 저장해두고 딕셔너리에 넣어봐서 이미 있는 값이면 방문된거고 없으면 새로 방문한 것이고

 

이를 이용한다면, 목적 배열 B도 딕셔너리에 미리 저장해둔 다음, 방문체크하다가 B가 나온다면 바로 바꾼 횟수를 return하면 된다

 

from collections import deque
from copy import deepcopy

h,w = map(int,input().split())

A = [list(map(int,input().split())) for _ in range(h)]
B = [list(map(int,input().split())) for _ in range(h)]

#2차원 배열의 모든 행을 튜플로 바꾼다
#딕셔너리에 저장할려면 리스트는 안되고 튜플로 바꿔줘야함
def to_tuple(A):
    
    return tuple(tuple(r) for r in A)

def bfs(A,B,h,w):

    p = deepcopy(A)
    
    #배열 자체를 상태로 두고
    visited = {to_tuple(A):1,to_tuple(B):-1}
    
    #키를 넣어봤을때, 값이 -1이라면 B가 되었다는 뜻이다
    if visited[to_tuple(p)] == -1:
        
        return 0

    queue = deque([(p,0)]) #(배열, 바꾼 횟수)

    while queue:
        
        p,c = queue.popleft()
        
        #행부터 바꿔보고
        for i in range(h-1):
                
            q = deepcopy(p)

            q[i],q[i+1] = q[i+1],q[i]
            
            #방문 상태 체크
            #키가 없다면 아직 방문하지 않은 배열 상태
            if visited.get(to_tuple(q),0) == 0:
                
                visited[to_tuple(q)] = 1
                queue.append((q,c+1))
            
            #value가 -1이라면 목적 배열 B가 되었다는 뜻이니 바로 바꾼 횟수 c+1을 return
            elif visited.get(to_tuple(q),0) == -1:
                
                return c+1
        
        #행을 바꿔봤으면 열도 바꿔본다
        for i in range(w-1):
            
            q = deepcopy(p)

            for y in range(h):
            
                q[y][i],q[y][i+1] = q[y][i+1],q[y][i]

            if visited.get(to_tuple(q),0) == 0:
                
                visited[to_tuple(q)] = 1
                queue.append((q,c+1))
            
            elif visited.get(to_tuple(q),0) == -1:
                
                return c+1
        
        #각 큐에 행끼리 바꾼 배열, 열끼리 바꾼 배열들이 들어가있는데..
        #매번 큐에서 꺼내면서 행끼리만 바꾼 배열은 또 열도 바꿔보고
        #열끼리만 바꾼 배열은 또 행도 바꿔보면서...
        #모든 행과 열을 서로 바꿔보는 완전탐색이 된다
    
    return -1

print(bfs(A,B,h,w))