[코드트리] 2개의 사탕

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/two-candies/description?page=1&pageSize=20

💻 문제 풀이 : C++

#include <iostream>
#include <cstring>
#include <algorithm>

#define MAP_SIZE 12

using namespace std;

struct Coord {
	int row;
	int col;
};

int N, M;
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 answer;

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

void INIT()
{
	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.row = i;
				RED.col = j;
			}
			else if (MAP[i][j] == 'B')
			{
				BLUE.row = i;
				BLUE.col = 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++;
		if (MAP[now_r][now_c] == 'O')
			break;
	}
}

void dfs(int r_r, int r_c, int b_r, int b_c, int cnt)
{
	if (answer <= cnt) return;
	// 10번 이내에 못 빼내는 경우
	if (cnt > 10) return;
	// 파란 사탕이 나온 경우
	if (MAP[b_r][b_c] == 'O') return;
	// 빨간 사탕만 나온 경우
	if (MAP[r_r][r_c] == 'O')
	{
		answer = min(answer, cnt);
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		// tmp 변수로 움직여야 함
		int tmp_red_row = r_r;
		int tmp_red_col = r_c;
		int rdist = 0;
		int tmp_blue_row = b_r;
		int tmp_blue_col = b_c;
		int bdist = 0;

		move(tmp_red_row, tmp_red_col, i, rdist);
		move(tmp_blue_row, tmp_blue_col, i, bdist);

		if (tmp_red_row == tmp_blue_row && tmp_red_col == tmp_blue_col && MAP[tmp_red_row][tmp_red_col] != 'O')
		{
			if (rdist > bdist)
			{
				tmp_red_row -= dr[i];
				tmp_red_col -= dc[i];
			}
			else {
				tmp_blue_row -= dr[i];
				tmp_blue_col -= dc[i];
			}
		}

		int debug = 0;
		if (!visited[tmp_red_row][tmp_red_col][tmp_blue_row][tmp_blue_col])
		{
			visited[tmp_red_row][tmp_red_col][tmp_blue_row][tmp_blue_col] = true;
			dfs(tmp_red_row, tmp_red_col, tmp_blue_row, tmp_blue_col, cnt + 1);
			visited[tmp_red_row][tmp_red_col][tmp_blue_row][tmp_blue_col] = false;
		}
	}
}

void SOLVE()
{
	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\n";
		return;
	}
	cout << answer << "\n";
}

int main()
{
	CLEAR();
	INIT();
	SOLVE();

	return 0;
}

---

📌 memo 😊

4차원 방문 확인 배열

visitied[RED.row][RED.col][BLUE.row][BLUE.col]
=> 두개의 구슬이 동시에 움직이기 때문...?!