[PCCP 기출문제] 4번 / 수레 움직이기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/250134

프로그래머스

 

재귀함수와 BFS 알고리즘을 통해 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. maze 벡터를 순회하며 빨간색 수레와 파란색 수레가 위치한 좌표를 구하고 해당 좌표를 각각 빨간색과 파란색 수레가 위치했었다고 visited 배열에 표시를 합니다.

2. 각 수레는 상하좌우로 움직일 수도 있고 가만히 서있을 수도 있습니다. 

2.1 각 턴마다 두 수레 모두 움직이지 않는 경우의 수를 제외한 24개 경우의 수를 시뮬레이션 돌리고 문제에서 주어진 조건에 성립할 경우 업데이트된 수레의 좌표와 증가된 턴을 매개변수로 넘겨 재귀함수를 다시 호출합니다.

2.2 두 수레 모두 각자의 도착 칸에 도착할 경우 answer를 업데이트해줍니다.

3. 2번에서 구한 answer를 반환하되 answer가 초기값일 경우 불가능한 케이스이므로 0을 반환해 줍니다.

 

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <iostream>
	using namespace std;
	const int INF = 987654321;
	const int MAX = 4;
	const int RED = 0;
	const int BLUE = 1;
	const int RED_GOAL = 3;
	const int BLUE_GOAL = 4;
	const int WALL = 5;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[5] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {0, 0}};
	int answer = INF;
	int N, M;
	pair<int, int> red, blue;
	bool visited[MAX][MAX][2];
	bool isOutOfBounds(int y, int x)
	{
	return y < 0 || y >= N || x < 0 || x >= M;
	}
	bool collapsed(int y, int x, int y2, int x2)
	{
	return y == y2 && x == x2;
	}
	bool overlapped(pair<int, int> redPos, pair<int, int> nextRedPos, pair<int, int> bluePos, pair<int, int> nextBluePos)
	{
	return redPos == nextBluePos && bluePos == nextRedPos;
	}
	bool bothArrivedAtGoals(pair<int, int> redPos, pair<int, int> bluePos, vector<vector<int>> &maze)
	{
	return maze[redPos.first][redPos.second] == RED_GOAL
	&& maze[bluePos.first][bluePos.second] == BLUE_GOAL;
	}
	void func(pair<int, int> redPos, pair<int, int> bluePos, int cnt, vector<vector<int>> &maze)
	{
	if (bothArrivedAtGoals(redPos, bluePos, maze))
	{
	answer = min(answer, cnt);
	return;
	}
	for (int k = 0; k < 5; k++)
	{
	int nextRedY = redPos.first + moveDir[k].y;
	int nextRedX = redPos.second + moveDir[k].x;
	if (isOutOfBounds(nextRedY, nextRedX)
	|| (maze[nextRedY][nextRedX] != RED_GOAL && visited[nextRedY][nextRedX][RED])
	|| maze[nextRedY][nextRedX] == WALL)
	{
	continue;
	}
	visited[nextRedY][nextRedX][RED] = true;
	for (int l = 0; l < 5; l++)
	{
	if (k == 4 && l == 4)
	{
	break;
	}
	int nextBlueY = bluePos.first + moveDir[l].y;
	int nextBlueX = bluePos.second + moveDir[l].x;
	if (isOutOfBounds(nextBlueY, nextBlueX)
	|| (maze[nextBlueY][nextBlueX] != BLUE_GOAL && visited[nextBlueY][nextBlueX][BLUE])
	|| maze[nextBlueY][nextBlueX] == WALL
	|| collapsed(nextRedY, nextRedX, nextBlueY, nextBlueX)
	|| overlapped(redPos, {nextRedY, nextRedX}, bluePos, {nextBlueY, nextBlueX}))
	{
	continue;
	}
	visited[nextBlueY][nextBlueX][BLUE] = true;
	func({nextRedY, nextRedX}, {nextBlueY, nextBlueX}, cnt + 1, maze);
	visited[nextBlueY][nextBlueX][BLUE] = false;
	}
	visited[nextRedY][nextRedX][RED] = false;
	}
	}
	int solution(vector<vector<int>> maze) {
	N = maze.size();
	M = maze[0].size();
	for (int y = 0; y < N; y++)
	{
	for (int x = 0; x < M; x++)
	{
	switch (maze[y][x])
	{
	case 1:
	red = {y, x};
	visited[y][x][RED] = true;
	break;
	case 2:
	blue = {y, x};
	visited[y][x][BLUE] = true;
	break;
	}
	}
	}
	func(red, blue, 0, maze);
	return answer == INF ? 0 : answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE 

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~