[삼성기출] 백준 - C++ 구슬탈출2

'구현'과 'BFS'를 이용한 문제이다.
참고,  velof.io/@madpotato1713/백준-13460-구슬탈출2

풀이
간단히 말해, 구슬의 이동경로를 모두 찾는다.

max count 가 10이고, map도 최대 가로, 세로의 길이가 10이기 때문에 가능한 방법일 것 같다.

 

BFS를 해결하기 위해, 재귀함수를 이용하여 풀었으며, 다음과 같은 순서로 알고리즘을 구현하였다.

1. 한쪽 방향으로 양 구슬의 움직임이 없을때까지 움직인다. 움직이는 방향(상, 하, 좌, 우)은 매개변수를 통해 받는다.
2. 움직임이 없다면(첫 구슬의 위치와 같다면) 곧바로 return
3. 빨간 구슬과 파란 구슬의 위치가 같다면, 위치를 조정해준다.
   예를 들어, '상' 위치로 움직였을 경우 빨간 구슬과 파란 구슬의 위치가 같았을 때, 처음의 y좌표가 빨간 구슬이 4, 파란 구슬이 5였다면 파란 구슬의 y 좌표값에 1을 더해준다.
4. 다음 이동 결과를 결정할 수 있도록 for문으로 상, 하, 좌, 우 위치정보를 차례대로 넘겨주며 동일 함수를 호출한다

구슬의 이동경로를 모두 찾아서 해결하였다.

 

Pseudo Code

int Solution(count, Red 위치, Blue 위치, 이동방향){

if(count > 10)
     return INF;
        
rx = Red 위치.x;
    ry = Red 위치.y;
    bx = Blue 위치.x;
    by = Blue 위치.y;
    
    res = INF;
    
While('.'로 Red 이동)
     if(hole)
         break;

    While('.'로 Blue 이동)
     if(hole)
         return res = INF;

if(Blue hole)
     return res;
if(Red/Blue 모두 움직이지 않음)
     return res = INF;
if(Red와 Blue 겹침)
     안 겹치게 Red/Blue 이동;

    for(i; 상/하/좌/우)
     res = min(res, Solution(count + 1, 이동된 Red 위치, 이동된 Blue 위치, i));

}

---

1. Solution 코드

2. 알아야 할 개념
1) 상하좌우 움직이는 (x, y) 좌표 구현

// 상하좌우 방향으로 움직이는 (x, y)좌표
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

for(int i = 0; i < 4; i++){
	x = x + dx[i];
    y = y + dy[i];
}