+ 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
+ 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다.
+ 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다.
+ 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다.
+ 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
+ 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다.
+ 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
+ 각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다.
+ 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다.
+ 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다.
+ 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
+ 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다.
+ 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다.
+ 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
+ 입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
+ 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 1을 없으면 0을 출력한다.
접근 방법 :
bfs 탐색 시 한 칸이 아닌 벽 또는 구멍을 만날 때까지 이동하도록 하고, queue의 경우 빨강, 파랑 구슬 각각의 큐를 생성한다. 구슬이 10번 이하로 움직였을 때 탈출해야하므로, 각 큐는 x, y 좌표, 횟수로 구성하도록 한다. 또, 특정 반례 조건에서 ( 구멍이 파란색 바로 옆이고, 빨강 구슬이 파랑구슬에 막혀 나갈 수 없을 때) 는 무한 loop를 돌 수 있으므로 visted 를 사용해 같은 곳을 반복해서 가지 않도록 한다.
풀이 순서 :
N과 M을 입력 받고, 해당 크기만큼의 맵의 정보를 입력 받는다.
이 때, 맵의 정보 해당 인덱스 값이 'R' 또는 'B' 라면 해당 좌표를 각각 red와 blue에 저장한다 (pair<int, int>)
visited의 red x, y좌표 blue x, y 좌표 = true를 하고, 각각의 queue를 생성해 좌표와 cost를 넣고 bfs 탐색을 수행한다.
BFS
각 구슬의 좌표, cost를 queue에서 pop한 뒤, 각각의 cost 중 하나라도 10을 넘으면 res=0을 주고 종료한다.
각각의 구슬 nx ny에 초기값 각각의 구슬 좌표를 넣어주고, 벽이나 구멍을 만날 때까지 쭉 이동해야하므로,
while 문을 사용해서 해당 조건을 충족할 때까지 이동시킨다.
각각의 구슬 nx, ny 값의 map 정보가 만약 블루가 먼저 들어갔다면 탐색 continue
red가 들어갔다면 res=1 하고, bfs 종료
각각의 구슬 nx ny가 같다면, cost (이동한 거리)가 높은게 다른 구슬보다 뒤에 있었던 것이므로, 해당 좌표에 -= dx, dy를 해준다.
만약 visted 각각의 구슬 좌표 nx ny가 true라면 이미 방문한 것이므로, 탐색 continue
아니라면 해당 좌표 visited에 true를 주고, 각각의 구슬 queue에 cost +1과 각 구슬 nx, ny 좌표를 넣어준다.
inseonyun
commented
1 year ago 
Source URL : https://www.acmicpc.net/problem/13459
문제 요구사항 :
접근 방법 : bfs 탐색 시 한 칸이 아닌 벽 또는 구멍을 만날 때까지 이동하도록 하고, queue의 경우 빨강, 파랑 구슬 각각의 큐를 생성한다. 구슬이 10번 이하로 움직였을 때 탈출해야하므로, 각 큐는 x, y 좌표, 횟수로 구성하도록 한다. 또, 특정 반례 조건에서 ( 구멍이 파란색 바로 옆이고, 빨강 구슬이 파랑구슬에 막혀 나갈 수 없을 때) 는 무한 loop를 돌 수 있으므로 visted 를 사용해 같은 곳을 반복해서 가지 않도록 한다.
풀이 순서 :