A. 문제설명
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. N*N 크기의 땅이 존재
2. 각 배열의 엔트리에는 0:빈칸, 1:나무가 주어짐
3. 그리고 아래와 같이 통나무의 처음 위치가 B로, 목적지가 E로 주어짐
B 0 0 1 1
B 0 0 0 0
B 0 0 0 0
1 1 0 0 0
E E E 0 04. 위 배열에서 통나무를 상하좌우로 이동, 혹은 90도 회전시켜 목적지로 이동시키고자 함
5. 통나무를 목적지까지 이동시키면서 걸리는 가장 최소의 단위 동작 횟수를 구하라
B. 접근법
BFS
처음에 문제를 DFS로 구현하였으나, 시간 초과로 BFS로 다시 구현하였다. 출발지와 목적지가 주어지고, 해당 경로에 도착하는 최소 단위 동작을 구하는 문제이니 BFS가 가장 효과적이라고 볼 수 있다.
문제에서 주의해야할 점은 다음과 같다.
1. BFS 탐사시, 그리고 방문 체크시 통나무의 방향정보 포함 0:수평, 1:수직
2. 3길이의 통나무의 일부분이 나무에 걸리거나 배열의 범위를 벗어나는지 체크
C. 풀이
1. BFS는 통나무의 가장 첫번째 좌상단에 가까운 좌표를 저장하여 탐사
2. 통나무 큐의 원소가 목적지의 원소와 동일하면 종료 및 탐사거리 반환
3. 통나무가 수평/수직일 때에 따라 상하좌우 이동 탐사 및 BFS 큐에 삽입
4. 통나무가 수평/수직일 때에 따라 90도 회전 각각 수행
5. 모든 큐가 빌때까지 탐사해도 목적지 도달 못할 시 0 반환
D. 내 코드
