[삼성기출/C++] 왕실의 기사 대결

https://www.codetree.ai/training-field/frequent-problems/problems/royal-knight-duel?&utm_source=clipboard&utm_medium=text

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

 

 방금 따끈따끈하게 3급 공채 코딩테스트 장소 공지가 올라왔다! 일요일 오전반이다. 일요일까지 열심히 달려보자.

 

 이번에 풀 문제는 23년도 하반기 오전 1번 문제이다! 마침 내가 시험을 보는 날에 해당하는 1번 문제이니, 깔끔하게 다 풀어보도록 하자. 문제가 어렵지는 않지만, 실수하기는 쉬운 문제이므로 공부하기 좋은 문제라고 생각한다. 그럼 문제를 보자.

 

 1. 돌다리도 "두드려 보고" 건너자.

 

 이 문제에서 가장 실수하기 쉬운 부분이다. 기사가 연쇄적으로 이동하므로, 일단 모든 이동할 수 있는 기사를 찾고, 그 기사들이 모두 이동 가능하다면, 실제로 이동시킬 수 있다. 하지만 기사들이 항상 이쁘게 연결되어있지는 않을 것이다. 예시를 들면 다음과 같다.

'

 위 그림에서 1번 기사를 오른쪽으로 옮긴다고 할 때, 2번에서 함정에 걸리지만, 나머지 3번~6번은 모두 옮길 수 있다는 결론이 나온다. 그러면 어떻게 이를 판단해야할까? 바로 DFS를 이용하는 것이다. 구체적인 예시는 다음과 같다.

bool can_move(int id, int dir) { 
	visited[id] = true;
	for (int i = 0; i < knight[id].h; i++) {
		for (int j = 0; j < knight[id].w; j++) {
			int ny = knight[id].r + i + dy[dir];
			int nx = knight[id].c + j + dx[dir];
			if (cant_go(ny, nx)) return false;
			if (is_knight(ny, nx, id) && visited[knight_array[ny][nx]] == 0) {
				if(can_move(knight_array[ny][nx], dir) == 0) return false;
			}
		}
	}
	return true;
}

 

 이런 식으로 처음 이동하려는 녀석을 visited에 방문 처리를 해주고 이후로는 방문하지 않은 기사를 방문하면서 재귀 함수를 구성한다면, 결국 어떤 기사에서 이동이 불가능한 경우 FALSE를 리턴하므로 이동하지 않으면 된다!

 이렇게 돌다리를 두드려보는 방식이 좋은 점은, 돌다리를 두드린 이후에는 이동할 수 있음이 "결정" 되어 있으므로, 마음놓고 모든 기사들을 다시 DFS로 탐색하면서 옮겨주면 된다.

 

2. 실수하지 않고 기사를 옮기는 방법

 

 그 다음으로 어려운 부분은, 기사를 "어떻게" 옮겨야 실수하지 않고 완벽하게 옮길 수 있냐는 것이다. 우선 다시 한번, 아까 그림을 보자.

'

 이 그림에서 함정이 없다고 생각하면, 1~6번 기사를 모두 오른쪽으로 1칸씩 옮겨줘야 한다. 어떻게 옮겨야 할까? 중복이 발생할 수도 있고, 탐색이 실패할 수도 있다.

 해법은, DFS를 하면서 리턴하기 직전에 옮겨주는 것이다. 이렇게 옮겨주면, DFS 트리에서 리프 노트(Leaf Node) 부터 한 칸씩 옮기므로, 무분별한 overwrite 없이 모든 부분을 실수 없이 옮길 수 있다. 그림으로 설명하면 다음과 같다. 리프노드부터 루트노드까지에 대한 travel이 이루어지는 모습이다.

 

 

 이러한 부분을 생각하면서 코드를 작성해주면 나머지는 쉽다. 전체 코드는 다음과 같다.

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void init() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); }

typedef struct knight {
	int r, c, h, w, k;
}Knight;

Knight knight[34];
int knight_array[44][44];
int land[44][44];
int l, n, q;
const int dy[] = { -1,0,1,0 }; // 상우하좌
const int dx[] = { 0,1,0,-1 };
int visited[34];
int hp[34];
int ret;

bool is_knight(int y, int x, int id) {
	if (knight_array[y][x] > 0 && knight_array[y][x] != id) return true;
	return false;
}

bool is_out(int y, int x) {
	if (y<1 || y>l || x<1 || x>l) return true;
	return false;
}

bool cant_go(int y, int x) {
	if (is_out(y, x) || land[y][x] == 2) return true;
	return false;
}

bool can_move(int id, int dir) { 
	visited[id] = true;
	for (int i = 0; i < knight[id].h; i++) {
		for (int j = 0; j < knight[id].w; j++) {
			int ny = knight[id].r + i + dy[dir];
			int nx = knight[id].c + j + dx[dir];
			if (cant_go(ny, nx)) return false;
			if (is_knight(ny, nx, id) && visited[knight_array[ny][nx]] == 0) {
				if(can_move(knight_array[ny][nx], dir) == 0) return false;
			}
		}
	}
	return true;
}

void move_knight(int id, int dir, int flag) {
	visited[id] = true;
	for (int i = 0; i < knight[id].h; i++) {
		for (int j = 0; j < knight[id].w; j++) {
			int ny = knight[id].r + i + dy[dir];
			int nx = knight[id].c + j + dx[dir];
			// 이동할 수 있음이 결정되었고, knight 연쇄 이동만 파악하면 된다.
			if (is_knight(ny, nx, id) && visited[knight_array[ny][nx]] == 0) {
				move_knight(knight_array[ny][nx], dir, 1); // flag == 1이면 데미지계산
			}
		}
	}
	// 원래의 흔적을 지워야한다.
	for (int i = 0; i < knight[id].h; i++) {
		for (int j = 0; j < knight[id].w; j++) {
			int y = knight[id].r + i;
			int x = knight[id].c + j;
			knight_array[y][x] = 0;
		}
	}
	// 이동한 곳 업데이트
	for (int i = 0; i < knight[id].h; i++) {
		for (int j = 0; j < knight[id].w; j++) {
			int ny = knight[id].r + i + dy[dir];
			int nx = knight[id].c + j + dx[dir];
			knight_array[ny][nx] = id;
			if (flag == 1 && land[ny][nx] == 1) { // flag == 1 이면 데미지계산
				knight[id].k--;
			}
		}
	}
	knight[id].r += dy[dir];
	knight[id].c += dx[dir];
	if (knight[id].k <= 0) { // 죽었다면 array에서 지우자.
		for (int i = 0; i < knight[id].h; i++) {
			for (int j = 0; j < knight[id].w; j++) {
				int y = knight[id].r + i;
				int x = knight[id].c + j;
				knight_array[y][x] = 0;
			}
		}
	}
	return;
}

void go(int id, int dir) {
	if (knight[id].k <= 0) return; // 죽으면 이동 x
	memset(visited, 0, sizeof(visited));
	if (can_move(id, dir) == 0) return; // 이동 못함
	memset(visited, 0, sizeof(visited));
	move_knight(id, dir, 0); // 이동 <- 이동할수있음이 결정됨.
}

void print() {
	for (int i = 1; i <= l; i++) {
		for (int j = 1; j <= l; j++) {
			cout << knight_array[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << "hp : ";
	for (int i = 1; i <= l; i++) cout << knight[i].k << " ";
	cout << '\n';
}

int main() {
	init();
	cin >> l >> n >> q;
	for (int i = 1; i <= l; i++) {
		for (int j = 1; j <= l; j++) {
			cin >> land[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		int r, c, h, w, k;
		cin >> r >> c >> h >> w >> k;
		knight[i] = { r,c,h,w,k };
		hp[i] = k;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				knight_array[r + y][c + x] = i;
			}
		}
	}
	//print();
	for (int i = 0; i < q; i++) {
		int id, dir;
		cin >> id >> dir;
		go(id, dir);
		//print();
	}
	for (int i = 1; i <= n; i++) {
		if (knight[i].k > 0) {
			ret += hp[i] - knight[i].k;
		}
	}
	cout << ret << '\n';
	return 0;
}

 

 이 문제에서도 1번의 풀이에서 AC를 받았다. 이대로라면 1번, 2번 모두 시험장에서 풀 수 있을 것 같다. 2번까지 다 풀면 사실상 면접에서도 프리패스이기 때문에, 시험날까지 열심히 달려보자.