[코드트리] 마법의 숲 탐색 with C++ (삼성기출)

https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

언어: C++, 소요시간: 18ms

 

 

 

접근방법

최근 삼성 기출의 구현문제는, 맵에 적은것과 별개로 또다른 리스트를 만들어서 접근하는 문제 스타일이 출제되고 있다.

쌓여가는 골렘을 표시하는 MAP 배열과 별개로,  골렘의 번호만 알면 바로 골렘의 중심위치, 출구위치, 출구방향을 알 수 있는 골렘 구조체 배열을 만들었다. 

 

구현한 함수들

input함수 (입력을 담는다)

solve함수 (문제 풀이를 구현한다)

→ moveGolem 함수 (골렘을 이동할 수 있을 때까지 이동한다. 맵을 벗어난다면 맵을 초기화한다.)

    → moveDown 함수 (골렘을 한 번 아래로 이동한다)

    →  moveLeft 함수 (골렘을 좌하로 한 번 이동한다)

    →  moveRight 함수 (골렘을 우하로 한 번 이동한다)

        →  golemRotate함수 (골렘의 출구를 반시계 또는 시계로 회전한다)

→ moveSpirit 함수 (골렘이 맵에 채워진다면, 정령을 bfs로 움직인다.)

 

 

 

 

 

 

구현시 고려사항

골렘 우선순위대로 이동

나 같은 경우는, 골렘의 우선순위(아래 이동 → 못 움직인다면 좌하로 굴러서 이동 → 못 움직인다면 우하로 굴러서 이동)

를 while문으로 구현했다. 만약 우하방향으로도 못 움직인다면 while문을 탈출한다. 

// 골렘 진입하기 
	while (1){
		if (moveDown(num)) {
			continue;
		}
		else {
			if (moveLeft(num))
				continue;
			else {
				if (moveRight(num))
					continue;
				else
					break;
			}
		}
	}

 

 

 

방향전환 구현

	if (rotateDir == 0) {
		curDir = (curDir + 3) % 4;			// 반시계 회전
	}
	else {
		curDir = (curDir + 1) % 4;			// 시계 회전
	}

방향을 바꾸고, 골렘 중심좌표에서 방향으로 한 칸 이동하면 출구좌표를 얻을 수 있다.

 

 

 

정령 bfs로 이동 시 for문 방향 4번 돌리는 코드 안에서:

 

ny nx로 못 움직이는 경우 체크

맵 범위를 벗어나는지 체크한다 -> 이미 방문한 곳인지 체크한다 , 맵이 빈칸인지 체크한다

 

맵이 양수일때(ny nx에 골렘이 있을때 체크)

ny nx와 현재위치 골렘 넘버가 같으면 이동할 수 있고, 큐에 넣고 최대 행을 max로 업데이트한다.

만약 ny nx와 현제위치 골렘 번호가 다르면 현재 now가 해당 골렘의 출구인지 체크한다. 출구라면 이동 할 수 있고, 큐에 넣고 최대 행을 max로 업데이트한다. 

 

 

 

최종코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

struct Node{
	int y;
	int x;
};

struct golem {
	int y;
	int x;
	int exitY;
	int exitX;
	int exitDir;
};

int R, C, K, isSpiritMove, answer;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int MAP[71][71];
int visited[71][71];
int cmdList[1001][2];
golem golemList[1001];

void input() {
	cin >> R >> C >> K;
	int tempC, tempDir;
	for (int i = 1; i <= K; i++){
		cin >> tempC >> tempDir;
		cmdList[i][0] = tempC-1;
		cmdList[i][1] = tempDir;
	}
}

// 골렘을 반시계 또는 시계로 움직이는 함수
void golemRotate(int num, int rotateDir) {

	int curDir = golemList[num].exitDir;
	if (rotateDir == 0) {
		curDir = (curDir + 3) % 4;			// 반시계 회전
	}
	else {
		curDir = (curDir + 1) % 4;			// 시계 회전
	}
	golemList[num].exitY = golemList[num].y + dy[curDir];
	golemList[num].exitX = golemList[num].x + dx[curDir];
	golemList[num].exitDir = curDir;
}

// 골렘을 한칸 밑으로 움직이는 함수
bool moveDown(int num) {

	golem curGolem = golemList[num];
	vector <Node> target;
	target.push_back({2, 0});
	target.push_back({ 1, -1 });
	target.push_back({ 1, 1 });

	for (int i = 0; i < target.size(); i++){
		int ny = curGolem.y + target[i].y;
		int nx = curGolem.x + target[i].x;

		if (ny >= R)	// 바닥을 뚫을 수 없다
			return false;

		if (ny >= 0 && nx >= 0 && ny < R && nx < C) {	// 만약 해당 칸이 다른 골렘이 있었다면 못간다
			if (MAP[ny][nx] > 0)
				return false;
		}
	}

	// 여기까지 왔다면 아래로 움직일 수 있다는 뜻.
	golemList[num] = { curGolem.y+1, curGolem.x, curGolem.exitY+1, curGolem.exitX, curGolem.exitDir };
	return true;
}

// 골렘을 한칸 좌하로 움직이는 함수
bool moveLeft(int num) {

	golem curGolem = golemList[num];
	vector <Node> target;
	target.push_back({ -1, -1 });
	target.push_back({ 0, -2 });
	target.push_back({ 1, -1 });
	target.push_back({ 1, -2 });
	target.push_back({ 2, -1 });

	for (int i = 0; i < target.size(); i++) {
		int ny = curGolem.y + target[i].y;
		int nx = curGolem.x + target[i].x;

		if (ny >= R)	// 바닥을 뚫을 수 없다
			return false;
		if (nx < 0 || nx >= C)	// 벽을 뚫을 수 없다
			return false;

		if (ny >= 0 && nx >= 0 && ny < R && nx < C) {	// 만약 해당 칸이 다른 골렘이 있었다면 못간다
			if (MAP[ny][nx] > 0)
				return false;
		}
	}

	// 여기까지 왔다면 아래로 움직일 수 있다는 뜻.
	golemList[num] = { curGolem.y+1, curGolem.x-1, curGolem.exitY+1, curGolem.exitX-1, curGolem.exitDir };
	golemRotate(num, 0);	// 반시계 회전
	return true;
}

// 골렘을 한칸 우하로 움직이는 함수
bool moveRight(int num) {

	golem curGolem = golemList[num];
	vector <Node> target;
	target.push_back({ -1, 1 });
	target.push_back({ 0, 2 });
	target.push_back({ 1, 1 });
	target.push_back({ 1, 2 });
	target.push_back({ 2, 1 });

	for (int i = 0; i < target.size(); i++) {
		int ny = curGolem.y + target[i].y;
		int nx = curGolem.x + target[i].x;

		if (ny >= R)	// 바닥을 뚫을 수 없다
			return false;
		if (nx < 0 || nx >= C)	// 벽을 뚫을 수 없다
			return false;

		if (ny >= 0 && nx >= 0 && ny < R && nx < C) {	// 만약 해당 칸이 다른 골렘이 있었다면 못간다
			if (MAP[ny][nx] > 0)
				return false;
		}
	}

	// 여기까지 왔다면 아래로 움직일 수 있다는 뜻.
	golemList[num] = { curGolem.y+1, curGolem.x+1, curGolem.exitY+1, curGolem.exitX+1, curGolem.exitDir };
	golemRotate(num, 1);	// 시계 회전
	return true;
}

// 골렘을 움직일 수 있을때까지 움직이고 맵에 표시하는 함수
void moveGolem(int num) {

	// 골렘 진입 준비 -> -2행에서 시작한다
	isSpiritMove = 1;
	golemList[num] = { -2, cmdList[num][0], -2, cmdList[num][0], cmdList[num][1] };
	golemList[num].exitY = golemList[num].y + dy[golemList[num].exitDir];
	golemList[num].exitX = golemList[num].x + dx[golemList[num].exitDir];

	// 골렘 진입하기 
	while (1){
		if (moveDown(num)) {
			continue;
		}
		else {
			if (moveLeft(num))
				continue;
			else {
				if (moveRight(num))
					continue;
				else
					break;
			}
		}
	}

	// 골렘이 맵 벗어났는지 체크하기
	golem curGolem = golemList[num];
	if (curGolem.y <= 0) {
		memset(MAP, 0, sizeof(MAP));
		isSpiritMove = 0;
		return;
	}

	// 맵에다 골렘 표시하기
	MAP[curGolem.y][curGolem.x] = num;
	for (int i = 0; i < 4; i++){
		int ny = curGolem.y + dy[i];
		int nx = curGolem.x + dx[i];
		MAP[ny][nx] = num;
	}
}

// 정령을 이동하고 최대 이동할 수 있는 행 더하는 함수
void moveSpirit(int num) {

	if (isSpiritMove == 0)
		return;				// 해당 골렘이 초과해서 골렘의 정령이 못 움직이는 경우


	// bfs 시작
	golem curGolem = golemList[num];
	memset(visited, 0, sizeof(visited));
	queue <Node> q;
	q.push({ curGolem.y, curGolem.x });
	visited[curGolem.y][curGolem.x] = 1;
	int maxRow = 0;

	while (!q.empty()){
		Node now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++){
			int ny = now.y + dy[i];
			int nx = now.x + dx[i];

			if (ny < 0 || nx < 0 || ny >= R || nx >= C)	// 맵 벗어나면 이동 못해
				continue;
			if (visited[ny][nx] == 1)	// 이미 벗어난 곳이면 이동 못해
				continue;
			if (MAP[ny][nx] == 0)		// 맵이 빈칸이면 이동 못해
				continue;

			// 골렘이 움직일 수 있는 경우
			int curGolemNum = MAP[now.y][now.x];
			int newGolemNum = MAP[ny][nx];
			
			if (curGolemNum == newGolemNum) {
				q.push({ ny, nx });
				visited[ny][nx] = 1;
				maxRow = max(maxRow, ny);
			}
				
			else {
				if (now.y == golemList[curGolemNum].exitY && now.x == golemList[curGolemNum].exitX) {
					q.push({ ny, nx });
					visited[ny][nx] = 1;
					maxRow = max(maxRow, ny);
				}
			}
		}
	}

	answer += (maxRow + 1);		// 정답 업데이트
}


void solve() {

	for (int num = 1; num <= K; num++)
	{
		moveGolem(num);
		moveSpirit(num);
	}

	cout << answer;
}

int main() {
	//freopen("sample_input.txt", "r", stdin);
	input();
	solve();
	return 0;
}