-
백준(BOJ) 1938번 통나무 옮기기알고리즘 풀이/백준(Boj) 2020. 3. 30. 14:03
문제 : https://www.acmicpc.net/problem/1938
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.
www.acmicpc.net
풀이 :
통나무의 가운데 부분의 좌표와 ( b2y와 b2x는 통나무의 중앙, e2y e2x는 목표지점의 중앙 )
상태가 세로인지 가로인지를 담아서 큐에 담은 후에 BFS를 통해 최소 경로를 찾는다.
세로인지 가로인지는 첫부분과 중앙부분의 x좌표를 비교해 차이가 0 이면 세로이고 차이가 0이 아니면 가로이다.
이때 d는 똑같은 좌표에서 회전이 가능하므로 3차원으로 만들어 가로인지 세로인지 상태를 판단해주어야 한다.
코드 ( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 11559번 Puyo Puyo (0) 2020.04.08 백준(BOJ) 17142번 연구소 3 (0) 2020.03.31 백준(BOJ) 18809번 Gaaaaaaaaaarden (0) 2020.03.28 백준(BOJ) 18808번 스티커 붙이기 (0) 2020.03.28 백준 BOJ(16637번) 괄호 추가하기 (0) 2020.03.21