[백준 13460] 구슬탈출 2

문제링크 : https://www.acmicpc.net/problem/13460

💻 문제 풀이 : C++

#include <iostream>
#include <cstring>
#include <vector>

#define MAP_SIZE 15

using namespace std;

struct Coord {
	int row;
	int col;
};

int N, M, answer;
char MAP[MAP_SIZE][MAP_SIZE];
bool visited[MAP_SIZE][MAP_SIZE][MAP_SIZE][MAP_SIZE];

Coord RED, BLUE;
int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };

int my_min(int a, int b)
{
	return a < b ? a : b;
}

void CLEAR()
{
	N = M = 0;
	memset(MAP, 0, sizeof(MAP));
	memset(visited, 0, sizeof(visited));
	answer = 2134567890;
}

void INPUT()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> MAP[i][j];
			if (MAP[i][j] == 'R')
				RED = { i, j };
			else if (MAP[i][j] == 'B')
				BLUE = { i, j };
		}
	}
}

/* 구슬 움직이기 */
void move(int &now_r, int &now_c, int dir, int &dist)
{
	while (MAP[now_r+dr[dir]][now_c+dc[dir]] != '#')
	{
		now_r += dr[dir];
		now_c += dc[dir];
		dist += 1;
		if (MAP[now_r][now_c] == 'O')
			break;
	}
}

void dfs(int r_now_r, int r_now_c, int b_now_r, int b_now_c, int cnt)
{
	int debug = 1;
	// 최소값보다 시고수가 많은 경우
	if (answer <= cnt) return;
	// 10번보다 더 움직이는 경우
	if (cnt > 10) return;
	// 파란구슬이 구멍에 들어간 경우
	if (MAP[b_now_r][b_now_c] == 'O') return;
	// 빨간구슬이 구멍에 들어간 경우
	if (MAP[r_now_r][r_now_c] == 'O')
	{
		answer = my_min(answer, cnt);
		return;
	}
	
	for (int i = 0; i < 4; i++)
	{
		int rnr = r_now_r, rnc = r_now_c, rdist = 0;
		int bnr = b_now_r, bnc = b_now_c, bdist = 0;
		
		// 빨간 구슬 이동
		move(rnr, rnc, i, rdist);
		// 파란 구슬 이동
		move(bnr, bnc, i, bdist);

		// 빨간 구슬과 파란 구슬이 부딪히는 경우
		if (MAP[rnr][rnc] != 'O' && rnr == bnr && rnc == bnc)
		{
			if (rdist > bdist) {
				rnr -= dr[i];
				rnc -= dc[i];
			}
			else {
				bnr -= dr[i];
				bnc -= dc[i];
			}
		}
		int debug = 1;

		if (!visited[rnr][rnc][bnr][bnc]) {
			visited[rnr][rnc][bnr][bnc] = true;
			dfs(rnr, rnc, bnr, bnc, cnt+1);
			visited[rnr][rnc][bnr][bnc] = false;
		}
	}
}

void SOLVE()
{
	int dist = 0;
	visited[RED.row][RED.col][BLUE.row][BLUE.col] = true;
	dfs(RED.row, RED.col, BLUE.row, BLUE.col, 0);
	if (answer == 2134567890)
	{
		cout << -1;
		return;
	}
	cout << answer << endl;
}

int main()
{
	int T;
	{
		CLEAR();
		INPUT();
		SOLVE();
	}

	return 0;
}

💻 문제 풀이 : Python

---

📌 memo

😊 Python

---

ref)
👍코드 참고
https://transferhwang.tistory.com/188