[백준] 13460 구슬탈출 2

[백준13460] 구슬탈출2

1. 입력을 받아 현재 각 구슬의 위치와, 구멍의 위치를 기록한다
2. BFS 시작한다
   각 구슬을 이동시킬때 구멍에 도달했거나 다음 이동할 장소가 벽이면 반복을 중단한다.
   고려해야할 경우는 다음과 같다.

• 빨간 구슬과 파란 구슬이 겹쳐 있을 경우 (일직성 상에 있을 경우)
  - 움직인 거리가 더 많은 것을 다시 원래 자리로 한칸 이동한다

//bfs탐색
#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

struct NODE {
	int depth, rx, ry, bx, by; //각 위치와 depth
};

int N, M; //입력
int fx, fy; //구멍의 위치
char map[10][10]; //맵
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
bool visit[10][10][10][10];


int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%s", map[i]);
	}
	int srx, sry, sbx, sby; //각 공 초기 위치

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 'R') {
				srx = i;
				sry = j;
			}
			else if (map[i][j] == 'B') {
				sbx = i;
				sby = j;
			}
			else if (map[i][j] == 'O') {
				fx = i;
				fy = j;
			}
		}
	}

	queue<NODE> q;
	q.push({ 0,srx,sry,sbx,sby }); //현재 공의 위치 push
	int ans = -1; 
	visit[srx][sry][sbx][sby] = true;

	while (!q.empty()) {
		NODE cur = q.front();
		q.pop();

		//종료 경우(깊이가 10 이상이거나 빨간 공이 구멍에 도착)
		if (cur.depth > 10) break;
		if (cur.rx == fx && cur.ry == fy) {
			ans = cur.depth;
			break;
		}

		for (int i = 0; i < 4; i++) {
			int rx = cur.rx;
			int ry = cur.ry;
			int bx = cur.bx;
			int by = cur.by;

			//빨간 구슬 이동
			while (1) {
				int nrx = rx + dx[i];
				int nry = ry + dy[i];
				//구멍에 도달했거나 이동할 장소가 벽이면 반복 중단
				if (map[nrx][nry] == '#' || map[rx][ry] == 'O') break;
				rx = nrx;
				ry = nry;
			}
			//파란 구슬 이동
			while (1) {
				int nbx = bx + dx[i];
				int nby = by + dy[i];
				if (map[nbx][nby] == '#' || map[bx][by] == 'O') break;
				bx = nbx;
				by = nby;
			}
			//빨간 구슬과 파란 구슬이 겹칠 경우
			if (rx == bx && ry == by) {
				if (map[bx][by] == 'O') continue; //파란 구슬이 구멍에 들어갈 경우 이 케이스 버리기
				//움직인 거리가 더 많은 것을 다시 원래자리로 한칸 이동
				if (abs(cur.rx - rx) + abs(cur.ry - ry) > abs(cur.bx - bx) + abs(cur.by - by)) {
					rx -= dx[i];
					ry -= dy[i];
				}
				else {
					bx -= dx[i];
					by -= dy[i];
				}
			}

			if (visit[rx][ry][bx][by]) continue; //방문한적이 있으면 이 경우 건너뛰기
			visit[rx][ry][bx][by] = 1; //방문 표시
			q.push({ cur.depth+1,rx,ry,bx,by });
		 }
	} //while 문 마지막

	printf("%d", ans);

	return 0;
}