[백준 / BOJ] 1938 통나무 옮기기

문제

출처 : https://www.acmicpc.net/problem/1938

1938번: 통나무 옮기기

N*N그리드에, 통나무(B)와 통나무를 옮겨야 하는 위치(E)가 주어진다.

 

통나무의 길이는 항상 3이며, 통나무를 옮겨야 하는 위치의 길이는 통나무의 길이와 같다. 통나무를 밀어서 E위치 까지 옮길려할때, 최소한의 이동횟수를 구하는 문제다.

 

통나무를 옮기는 방법은 (상,하,좌,우, 90도 회전) 이렇게 총 5가지가 있다.

 

풀이

BFS를 이용한 시뮬레이션 문제였다.

 

문제가 말하는바 그대로 구현하면되는데, BFS를 수행할때, 같은 위치를 두번이상 봐주지않기위해, 체크를해줘야한다.

이때, 탐색마다 N*N을 전부 봐주며 중복을 체크하면 탐색마다 2500번 반복하므로, 너무 오래걸린다. (이렇게 체크하는 방법이 있는지도 의문이다.)

따라서, 체크를 해줄때 통나무의 현재위치를 가져와 체크를해준다.

예를들어, 통나무의 위치가 

(1,1) (2,1) (3,1) 이라면, 통나무가 해당 위치에 있을때의 값을 봐주면된다. 이때, 통나무의 위치는 y <= 50 x <= 50 이므로, 배열로 선언할경우,

int check[50][50][50][50][50][50] 이 되어서, 선언자체가 안된다. 따라서, map자료구조를 이용해 체크를 해줘야한다.

(통나무가 상태는 최대 5000개 정도..이므로 map의 최대크기 또한 5000개 정도 된다.)

map<vector<pair<int,int> >,int> 와 같이 선언해서 봐준다.

 

check해주는법만 떠올리면 나머지는 문제 그대로 구현하면 되는 문제였다.

 

주의할점이

1. 90도 회전할때, 왼쪽으로 90도 오른쪽으로 90도를 따로 생각해주면안된다.

(문제에도 명시되어있긴한데, 제대로 안읽고 풀었다가 이거때문에 1시간가량 디버깅했다...)

다음과 같은경우, (현실세계에서)오른쪽으로 회전시키면, 90도 회전할수는있지만, 이 문제에서는 회전을 못시킨다.

1 B 0

0 B 0

0 B 0

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1938%20%ED%86%B5%EB%82%98%EB%AC%B4%20%EC%98%AE%EA%B8%B0%EA%B8%B0/main.cpp

devxb/JJUNalgo