[기출문제] 마법의 숲 탐색

코드트리 기출문제에 있는 문제를 풀었다. 왜냐하면, 극한의 구현 문제이기 때문이다. 집중을 빡하고 풀어줘야지 실력도 상승하고 긴장감도 유지할 수 있기 때문이다. 그렇기에 해당 문제를 해결해보았다.

문제 유형은 정말 4~5가지의 알고리즘 문제를 한문제에 합쳐둔것 처럼 어렵다. 하지만 차근차근 문제를 풀어나가다 보면 어느순간 해결이 되어있는데 그 짜릿함이 있다. 그래서 오랜만에 구현문제들로 풀어보았다. 요즘은 다른 유형이 생겨났던데 굉장히 어려워서 그거는 풀지 않았다.

해당 문제는 범위를 늘려줘야하는 것에 키포인트가 있다고 생각한다. 골렘이 초반에 필요한 열은 3칸이다. 행은 뭐 신경쓸 필요는 없고, 그래서 열의 길이보다 +3칸 늘려줘서 거기서부터 시작하는 것이 좋다.
그래야 생각도 편해진다. 대신 열의 길이를 늘렸기 때문에 score는 -3을 해줘야한다. 당연한것이다. 그리고 항상 isRange()라는 함수를 많이 사용하게 되는데, 그 범위 또한 늘려주고 줄여주고 해줘야한다. 당연하다.

 

그리고 해당 문제를 해결할때는 글을 잘 못 읽어서 문제가 되었다. 나는 자리를 찾으려고 좌측으로 끝까지 이동해서 내려갈 곳을 찾고 없다면 우측으로 끝까지 이동해서 찾는 것인줄 알았는데... 그게 아니더라!

단 한번 이동해보고 판단하는 것이더라 항상 글이 긴 내용을 정리를 잘하고 설계를 잘하고 들어가야하는데 매번 오만함이 나를 힘들게 한다. 항상 겸손하자! 아래는 정답 코드이다 주석을 달아놨으니 보기 나쁘지만 이런 문제를 풀때는 주석이 필수이다.

#include<iostream>
#include<queue>
#include<cstring>

#define MAX 77
using namespace std;

struct Golem{
	
	int centerY;
	int centerX;
	int exits;
	
};

Golem golems[1010];
int answer,n,m,k,x,exits,board[MAX][MAX],visited[MAX][MAX],exitCheck[MAX][MAX];

const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1}; // n, e, s, w

int checkMove[3] = {2,3,1};
int checkDir[4][4] = {{},{0,1,2},{1,2,3},{2,3,0}};

void init(){
	
	/*
		골렘은 5개 모양으로 이루어져 있고, 그 위치가 마이너스에
		위치해 있으면 안된다.
		
		그렇기 때문에 골렘이 있을 수 있는 위 세칸을 비워두는데
		이 부분을 1 ~ 3 까지로 정한다. 
		
		그래서 초기 골렘의 위치는 2가 된다. 
	*/ 
	
	answer = 0;
	cin >> n >> m >> k;
	
	// 골렘의 숫자도, 1부터 k까지 이루어진다. 0이 된다면 끔찍! 
	for(int i = 1; i <= k; i++){
		cin >> x >> exits;
		golems[i] = {2,x,exits};
	}
	
}

int isRange(int y, int x){
	// 그래서 골렘의 범위는 1부터 n + 3까지로 정했다.
	// 왜냐하면 처음 내려오면 골렘의 중요부위는 4에 위치하게 되고
	// 머리 부분은 2에 위치하게되는데, 그렇게되면 range범위에서 걸린다.
	// 일단 위 3칸도 현재는 나의 편이라고 생각하자. 
	return 1 <= y && y <= n+3 && 1 <= x && x <= m;
}

int isNotRange(int y, int x){
	// 이제 여기부터는 내 범위가 아니다.
	// 1 ~ 3은 나의 범위가 아님을 이해하자. 
	return 1 <= y && y <= 3 && 1 <= x && x <= m;
} 

int moveDown(int y, int x, int golemNumber) {
	
	// moveDown 부분이다. 방향은 아래를 가리키고 있다.
	// 이전에 나는 mock up table을 만들어서 3방향이 비워져있는지 파악했다. 
	int dir = 2;
	int check = true;
	
	int ny = y + dy[dir];
	int nx = x + dx[dir]; // 현재 아래로 내려갈 것이기때문에, 아래에서 3방향을 살펴보자. 
	
	for(int i = 0; i < 3; i++){
		// 3방향을 살펴보자. checDir[down][0~2]; 
		int nny = ny + dy[checkDir[dir][i]];
		int nnx = nx + dx[checkDir[dir][i]];
		
		// board에 있는지 없는지 있다면 이동하지 못한다. 
		if(board[nny][nnx]) check = false; // 하나라도 false면 이동 불가 
		// 범위 내로 있는지 알아야한다. 끝까지 내려갈 순 없다.
		// 물론 for문n이 막아줄것이다. 하지만 좌우도 있지 않겠는가? 
		if(!isRange(nny,nnx)) check = false;	
	}
	
	// 아직은 업데이틀 해줄 필요가 없음. 
	// 출구도 바뀌지 않고, 배열에서만 업데이트를 해주면 됨.
	// 만약 내려가는 것이 통과가 됐다면? 현재 정령의 위치를 바꿔주게 된다. 
	if(check){
		golems[golemNumber].centerX = nx;
		golems[golemNumber].centerY = ny;
	}
	
	return check; 
}
// 서쪽으로 이동했지만, 아래로 내려가지 못했다면? 
int moveLeft(int y, int x, int golemNumber) {
	
	int dir = 3;
	int check = true;
	
	int ny = y + dy[dir];
	int nx = x + dx[dir];
	
	for(int i = 0; i < 3; i++){
		int nny = ny + dy[checkDir[dir][i]];
		int nnx = nx + dx[checkDir[dir][i]];
		
		if(board[nny][nnx]) check = false; // 하나라도 false면 이동 불가 
		if(!isRange(nny,nnx)) check = false;	
	}
	
	// 아직은 업데이틀 해줄 필요가 없음. 
	// 출구도 바뀌지 않고, 배열에서만 업데이트를 해주면 됨.
	
	if(check){
		golems[golemNumber].centerX = nx;
		golems[golemNumber].centerY = ny;
	}
	
	return check; 
}

int moveRight(int y, int x, int golemNumber){
	
	int dir = 1;
	int check = true;
	
	int ny = y + dy[dir];
	int nx = x + dx[dir];
	
	for(int i = 0; i < 3; i++){
		int nny = ny + dy[checkDir[dir][i]];
		int nnx = nx + dx[checkDir[dir][i]];
		
		if(board[nny][nnx]) check = false; // 하나라도 false면 이동 불가 
		if(!isRange(nny,nnx)) check = false;	
	}
	
	// 아직은 업데이틀 해줄 필요가 없음. 
	// 출구도 바뀌지 않고, 배열에서만 업데이트를 해주면 됨.
	
	if(check){
		golems[golemNumber].centerX = nx;
		golems[golemNumber].centerY = ny;
	}
	
	return check; 
}

struct INFO{
	
	int y;
	int x;
	int number;
	
};

void bfsGolem(int y, int x, int golemNumber){
	//우리에게 필요한건, 골렘의 위치, 그리고 골렘의 번호이다. 
	memset(visited,0,sizeof(visited));
	queue<INFO> q;
	q.push({y,x,golemNumber});
	visited[y][x] = 1;
	
	int downest = -1; // 제일 낮은곳을 -1로 설정해보자. 
	
	while(!q.empty()){
		
		int y = q.front().y;
		int x = q.front().x;
		int number = q.front().number;
		q.pop();
		
		// 매번 위치를 파악해보자. 위치가 다른 방식으로 낮을 수 있다. 
		if(downest <= y){
			downest = y;
		}
		
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			// 방향이동했다면? 
			
			// 방문했다면? 그대로 
			if(visited[ny][nx]) continue;
			// 범위를 벗어났다면? 그대로 진행, 1,2,3 내부엔 없다 어차피 
			if(!isRange(ny,nx)) continue;
			// 골렘이 없는 곳이라면? 그대로 진행 
			if(!board[ny][nx]) continue;
			// board[ny][nx]가 0초과이고, 그 전자리가 탈출자리라면?
			// 이동이 가능핟. 이때만 이동이 가능하다. 
			if(board[ny][nx] != number && exitCheck[y][x]) {
				visited[ny][nx] = 1;
				// 그리고 현재 번호를 변경해주자. 
				q.push({ny,nx,board[ny][nx]});
			}
			// 인접한 녀석이 나랑 번호가 같다면? 
			// 방문처리를 해주자. 
			else if(board[ny][nx] == number) {
				visited[ny][nx] = 1;
				q.push({ny,nx,number});
			}
		}
		
	}
	
//	cout << "move golem!" << golemNumber << "\n";
//	
//	for(int i = 1; i <= n + 3; i++){
//		for(int j = 1; j <= m; j++){
//			cout << visited[i][j] << " ";
//		}
//		cout << "\n";
//	}
//	
//	
//	cout <<"down ! : "<< downest << "\n";
	
	// 현재 위치는 +3을 해주었기 떄문에 -3을 해줘야한다. 
	answer += (downest - 3);
	
}

void clearBoard() {
	
	memset(board,0,sizeof(board));
	memset(exitCheck,0,sizeof(exitCheck));
	
}

void moveGolem(Golem g, int golemNumber) {
	
	// 골렘이 이동을 시작한다.
	// 골렘의 현재 상태가 주어진다.
	// y,x,exit,golemNumber이렇게 4개가 주어진다. 
	
	// 매번 이동상황마다 현 상태가 바뀌기 때문에, 이렇게 처리해야한다. 
	for(int i = 0; i < n; i++){
		
		int y = golems[golemNumber].centerY;
		int x = golems[golemNumber].centerX;
		int exits = golems[golemNumber].exits;
		
		// 현재 우선순위를 나타내주고있다. 
		
		// 일단 한칸 내려보는 것부터 시작을 하자. 
		if(moveDown(y,x,golemNumber)) continue;
		// left 이동도 같은 부분이다. 좌측으로 이동해서 3방향을 살펴보자. 
		if(moveLeft(y,x,golemNumber)){
			// 좌측 이동이 되었다면? 정령의 위치를 바꾸어줬기 떄문에, 정령의 위치를 매개변수로 다시 넣는다. 
			if(moveDown(golems[golemNumber].centerY, golems[golemNumber].centerX,golemNumber)) {
				// 방향전환
				// 방향전환해서 다운까지 성공했다면? 출구가 바뀌게 된다. 
				// 이동후 정령의 위치를 바꿔주기 때문에, 정령은 바꾸지 않아도 된다. 
				exits -= 1;
				if(exits < 0) exits = 3; 
				golems[golemNumber].exits = exits;
				continue;
			}
			else{
				// 내려가지 못했다면?  정령의 위치를 원상복귀한다. 
				// 정령의 위치를 재배치해주고 
				golems[golemNumber].centerY = y;
				golems[golemNumber].centerX = x;
			} 
		}
		// 우측 이동도 생각해보자. 
		if(moveRight(y,x,golemNumber)) {
			if(moveDown(golems[golemNumber].centerY, golems[golemNumber].centerX,golemNumber)) {
				// 방향전환 
				exits += 1;
				if(exits == 4) exits = 0;
				golems[golemNumber].exits = exits;
				continue;
			}
			else {
				golems[golemNumber].centerY = y;
				golems[golemNumber].centerX = x;
			}
		}
		else break;
		
	}
	
	// 위치 변화된곳 update 해주고, 
	// 해당 위치에서 4방향중에 범위를 벗어난 녀석이 있는지 파악하자. 
	int chk = 0;
	int y = golems[golemNumber].centerY;
	int x = golems[golemNumber].centerX;
	int exits = golems[golemNumber].exits;
	
	int ey = y + dy[exits];
	int ex = x + dx[exits];
	
	exitCheck[ey][ex] = 1;
	
	board[y][x] = golemNumber;
	
	// 골렘의 위치, 출구 방향, 출구 위치 전부 주어졌다. 
	
	
	// board 업데이트 해주기 
	// 4방향을 모두 체크하고, 만약 단 하나라도 범위를 벗어났다면? 
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		board[ny][nx] = golemNumber;
		
		if(isNotRange(ny,nx)) chk = 1;
	}
	
	if(chk) {
		
		// 숲속에 있는 골렘들 전부 빠져나가기. 
		// 숲속 골렘들을 전부 제거해주는 역할을 한다.
		// 물론 현재 정령은 더하지 않는다. 
		clearBoard();
		//clearExit();
		
	} else{
		
		// 최대한 남쪽으로 내려가는 골렘들 생각하기. 
		// bfs 돌리기. 현재 위치(서있는 골렘)가 출구라면?
		// 그리고 이제 최대한 내려가보자. 
		bfsGolem(y,x,golemNumber);
	}
	
}

void printBoard() {
	
	cout << "print board!" << "\n";
	for(int i = 1; i <= n+3; i++){
		for(int j = 1; j<= m; j++){
			cout << board[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	
	cout << "print exit board!" << "\n";
	for(int i = 1; i <= n+3; i++){
		for(int j = 1; j<= m; j++){
			cout << exitCheck[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	
	for(int i = 1; i <= k; i++){
		cout << "number : " << i << "\n";
		cout << "golems exits : "<< golems[i].exits << "\n";
	}
	
}

void solve() {
	
	for(int i = 1; i <= k; i++){
		moveGolem(golems[i],i);
		//printBoard();
	}
	
}

int main() {
	
	init();
	solve();
	cout << answer;
	
	return 0;
}