[Algorithm][C++] BOJ 13460 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

풀이 핵심

1. 최소 구슬을 굴리는 (기울이는) 횟수 구한는 문제 --> BFS로 풀이

 

2. 빨간 구슬, 파란 구슬의 시작 위치를 red_sr, red_sc, blue_sr, blue_sc 에 저장한다.

 

3. 4차원 배열인 check 배열을 활용해 중복 방문을 방지 한다. 

...
bool check[10][10][10][10];
...
// ex) check[red_sr][red_sc][blue_sr][blue_sc] = true;

 

4. 빨간 구슬, 파란 구슬 위치 정보와 구슬을 굴리는 (기울이는) 횟수 정보가 담긴 INFO struct를 만들어 큐에 push하고 pop 하는 방식으로 BFS 를 구현한다.

 

5. 현재(INFO cur) time(cur.time)이 10보다 크면 -1을 return 한다. 여기서  time은 구슬을 굴리는 (기울이는) 횟수이다.

 

6. 현재 (INFO cur) 빨간 구슬이 도착점('O')이고 파란 구슬은 도착점('O')이 아니면 현재 (INFO cur) 의 time(cur.time)을 return 한다. 

 

7. 그렇지 않으면 4방향을 탐색하는 for문으로 들어간다.

• 먼저 빨간 구슬이 벽('#')을 만나거나 도착점('O')을 만날 때 까지 현재 방향(dir)으로 위치를 증가시킨다.
• 빨간 구슬을 이동시키는 반복문이 끝나고 빨간 구슬 위치가 벽이라면 현재 방향의 반대 방향으로 한 칸 이동한다.
• 파란 구슬도 빨간 구슬처럼 이동 시킨다.
• 파란 구슬을 이동시키는 반복문이 끝나고 파란 구슬 위치가 벽이라면 현재 방향의 반대 방향으로 한 칸 이동한다.
• 만약 빨간 구슬과 파란 구슬의 위치가 같으면서 도착점이 아닐 경우 이동을 많이 한 구슬을 현재 방향의 반대 방향으로 한 칸 이동한다.
• 이동 시킨 빨간 구슬, 파란 구슬의 위치가 이미 방문한 곳이라면 (check[next.red_r][next.red_c][next.blue_r][next.blue.c] == true) 다른 방향을 탐색한다. (continue)
• 파란 구슬의 위치가 도착점이라면 다른 방향을 탐색한다. (continue)
• 위의 조건들에 걸리지 않고 잘 통과했다면 이동시킨 구슬의 위치를 방문했다고 표시하고 현재 구슬을 굴린 횟수를 하나 증가하여 (next.time++) 큐에 push 한다 (q.push(next)).

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int N, M;
int red_sr, red_sc, blue_sr, blue_sc; // 빨강/파랑 구슬 시작 위치
char map[10][10]; 
bool check[10][10][10][10]; // 중복 방문 확인용
struct INFO {
	int red_r, red_c;
	int blue_r, blue_c;
	int time; // 구슬을 굴린 (기울인) 횟수
};
const int dr[] = { 1,-1,0,0 };
const int dc[] = { 0,0,1,-1 };

int BFS() {
	int ret = -1;
	queue<INFO> q;
	q.push({ red_sr, red_sc, blue_sr, blue_sc, 0 });
	check[red_sr][red_sc][blue_sr][blue_sc] = true;
	while (!q.empty()) {
		INFO cur = q.front();
		 q.pop();
		 if (cur.time > 10) { // 구슬을 굴린 (기울인) 횟수가 10보다 크면 종료
			 break;
		 }
         // 빨간 구슬만 도착점에 도착할 경우 굴린 횟수 return
		if (map[cur.red_r][cur.red_c] == 'O' && map[cur.blue_r][cur.blue_c] != 'O') {
			ret = cur.time;
			break;
		}
		for (int dir = 0; dir < 4; dir++) {
			INFO next = cur;
            // 빨강 구슬 이동시키기
			while (map[next.red_r][next.red_c] != '#' &&\
				map[next.red_r][next.red_c] != 'O') {
				next.red_r += dr[dir];
				next.red_c += dc[dir];
			}
            // 빨강 구슬 위치가 벽이면 한 칸 뒤로
			if (map[next.red_r][next.red_c] == '#') {
				next.red_r -= dr[dir];
				next.red_c -= dc[dir];
			}
            // 파랑 구슬 이동시키기
			while (map[next.blue_r][next.blue_c] != '#' && \
				map[next.blue_r][next.blue_c] != 'O') {
				next.blue_r += dr[dir];
				next.blue_c += dc[dir];
			}
            // 파랑 구슬 위치가 벽이면 한 칸 뒤로
			if (map[next.blue_r][next.blue_c] == '#') {
				next.blue_r -= dr[dir];
				next.blue_c -= dc[dir];
			}
            // 만약 빨강 / 파랑 구슬 위치가 같다면 더 많이 이동한 구슬 한 칸 뒤로
			if (next.red_r == next.blue_r && next.red_c == next.blue_c && map[next.red_r][next.red_c] != 'O') {
				int red_length = abs(cur.red_r - next.red_r) + \
					abs(cur.red_c - next.red_c);
				int blue_length = abs(cur.blue_r - next.blue_r) + \
					abs(cur.blue_c - next.blue_c);
				if (red_length < blue_length) {
					next.blue_r -= dr[dir];
					next.blue_c -= dc[dir];
				}
				else {
					next.red_r -= dr[dir];
					next.red_c -= dc[dir];
				}
			}
			// 이미 방문했던 빨강 / 파랑 구슬 위치 조합이라면 다른 방향 탐색
			if (check[next.red_r][next.red_c][next.blue_r][next.blue_c]) {
				continue;
			}
			// 빨강 구슬의 위치와 관계 없이 파랑 구슬이 도착점에 도착하면 다른 방향 탐색
			if (map[next.blue_r][next.blue_c] == 'O') {
				continue;
			}

			check[next.red_r][next.red_c][next.blue_r][next.blue_c] = true;
			next.time++;
			q.push(next);
		}
	}
	return ret;
}

int main() {
	scanf("%d %d", &N, &M);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf(" %c", &map[r][c]);
			if (map[r][c] == 'R') {
				red_sr = r, red_sc = c;
				map[r][c] = '.';
			}
			else if (map[r][c] == 'B') {
				blue_sr = r, blue_sc = c;
				map[r][c] = '.';
			}
		}
	}
	int ans = BFS();
	printf("%d", ans);
	return 0;
}

 

이전에 풀어봤을 때는 너무 조건이 많은거 아니야? BFS로 푸는 건 맞는거 같은데... 라는 생각으로 풀지 못했던 문제였다.

풀어서 너무 뿌듯핟..

키보드 산 보람이 있다!