[백준] 13460 구슬 탈출 2

남혁준 2019. 12. 27. 17:11

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드

www.acmicpc.net

bfs문제 였습니다.

문제를 정확히 읽어야 한다는 교훈을 준 문제였습니다.

숫자 0과 영어 O를 헷갈리면 안됩니다..

풀이과정

우선 현재 R과 B의 좌표를 알아내서 큐에담는다

1. 현재 큐의 사이즈만큼 반복문을 돌린다. (-> 큐에담긴 요소가 모두 소진되면 1회 이동 으로 생각)

2. 현재 좌표가 R만 구멍에 빠졋는지 검사한다. 아닐경우 아래를 반복한다.

R과 B를 동/서/남/북 으로 4차례 굴린다
R과 B가 같은 위치에 있다면 더 많이 움직인 구슬을 왔던길로 한칸 미룬다.
최종 도착지의 좌표가 방문 안했던 곳이면 큐에 담는다

3. 큐의 사이즈 만큼 반복문이 끝난후 10회 이상 이동 했으면 -1을 출력하고 종료한다.

아니면 횟수 증가 후 1. 로 돌아간다.

*visited 배열은 단순히 ry,rx,by,bx의 좌표를 동시에 확인하기 위한 배열로 사용했습니다.