[백준 / BOJ] 1035 조각 움직이기

문제

출처 : www.acmicpc.net/problem/1035

1035번: 조각 움직이기

5*5크기의 보드에 최대 5개의 조각이있다. 이 조각을 적절히 움직여서 모든 조각이 연결되도록 할려고한다. 

조각은 상하좌우 한칸으로 이동시킬수 있다고할때, 모든 조각을 연결하는 최소한의 이동 횟수를 구하는 문제다.

 

풀이

처음에는(1년전??) BFS로 풀려했는데, BFS는 항상 최단경로를 보장하므로 하나의 조각을 기준으로 잡고 나머지 조각을 해당 조각으로 이동하는 횟수를 BFS로 구해주는로직을짰었음 결국 반례를 못찾고 접었다가 이제서야 풀게됐는데,

보드의 크기가 5*5 조각의 개수가 5개이므로 단순하게 모든경우를 다 봐줘도 된다. 이때, 비트마스킹을 이용해 같은 모양을 방문하는 경우를 없애 시간을 줄여줘야한다.

 

시간과 메모리?를 줄이기위해 몇가지 조건을 넣어줬는데,

1. 보드의 크기가 5*5이므로 모든 조각을 모으는데 최대 13을 넘지않는다. (문제에서 주어진 예제가 최악의 경우일듯) 따라서, 탐색횟수가 13보다 크거나같아지면 바로 return한다.

 

2. 비트마스킹을 이용해서 같은 보드모양을 두번 방문하지 않도록 체크해줬다. 예를들어, 다음과 같은 보드 모양을 비트로 표현하면

보드 :

* . . . *

. . . . .

. . . . .

. . . . .

* . . . *

비트 : 10001000000000000000100010

이된다. 위 비트를 맨 오른쪽부터 5*5보드를 1차원배열로 만들었을때의 인덱스라고 생각하자 그럼 각 비트가 표현하는 인덱스는

25 24 23 . . . 8 7 6 5 4 3 2 1 0 이 된다. 해당 인덱스에 조각이있다면 1 아니라면 0으로 표시해서 보드의 모양을 체크해준다.

 

3. 보드의 크기가 5*5 = 25 이다. 이를 비트마스킹으로 표현하려면 (1 << 26) = 약 60,000,000 인데, 배열의 선언가능 범위를 벗어난다. (천만벗어나면 에러떴던거같음) 따라서, 배열로 체크해주는게 아닌, map구조를 이용해서 체크해줬다.

map[비트] = 해당비트모양이 만들어질때까지 최소이동횟수

 

4. 보드에 있는 조각의 위치를 (따로 보드 탐색없이)바로 알수있도록, 벡터에넣고 탐색해줬다.

vector<pair<int,int> > vec -> 조각의 y,x인덱스

 

 

위 조건들을 생각하면서 백트래킹으로 모든 경우를 다 봐주면된다. 

 

아래는 계속틀리길래 찾은 반례다

 

*..**
.....
*.*..
.....
.....

 

답 : 5 

조각이 겹치지 않도록 조심하자

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1035%20%EC%A1%B0%EA%B0%81%20%EC%9B%80%EC%A7%81%EC%9D%B4%EA%B8%B0/main.cpp

devxb/JJUNalgo