[코드트리] 술래 잡기 (C++)

[문제]

https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek/description?page=1&pageSize=20

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

[설명]

읽을때부터 좀 그랬는데 생각보다 까다로웠던 문제였다. 소용돌이로 가는건 해봤는데 돌아오는 건 또 안해봤구나...구현자체는 빨리했는데 예외처리할게 좀 많았다.

까다로웠던 것들은

- 0,0에 도착했을때 방향전환 후 처리과정

- 거꾸로 돌때는 두번째부터 이동거리 감소됨 (첫번째 아래로 갈때는 오른쪽으로 가는 횟수 안줄어듬...)

- 바로 방향전환한다! 라는 것을 인지못하고 마지막으로 오른쪽 방향을 향했을때 count++을 하는 실수 등.이거때문에 한참 해멨다.

- 또 바보같이 턴수를 의미하는 t 을 while문에서 돌게해서 오류가있었다. for문 마다 t를 넣고 나가는 조건도 for문마다 넣어줘서 해결했다. 

 

[코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define X first
#define Y second


int N, M, H, K;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1}; //상, 우, 하, 좌
int board[100][100];
int dis[100][100];

int score;
int t;
pair <int, int> chaser;
int c_dir; //술래 방향

struct runner {
	int num;
	int x, y;
	int dir; //dir: 1 우, 2: 하
	bool out;
};
vector <runner> runners;

void runner_move(runner me) {
	if (dis[me.x][me.y] <= 3) {
		int nx = me.x + dx[me.dir];
		int ny = me.y + dy[me.dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) { //격자밖
			me.dir = (me.dir + 2) % 4;
			nx = me.x + dx[me.dir];
			ny = me.y + dy[me.dir];
		}
		if (nx == chaser.X && ny == chaser.Y) {
			runners[me.num] = me;
			return;
		}
		else {
			if (board[me.x][me.y] > 0) board[me.x][me.y]--; // 이전 좌표의 사람 한병 감소
			me.x = nx;
			me.y = ny;
			if (board[me.x][me.y] >= 0) board[me.x][me.y]++; // 이전 좌표의 사람 한병 감소
			runners[me.num] = me;
		}
	}
}
void BFS() {
	bool vis[101][101] = { false, };
	queue <pair<int, int>> q;
	dis[chaser.X][chaser.Y] = 0;
	q.push(chaser);
	while (!q.empty()) {
		pair <int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];	
			if (vis[nx][ny]) continue;
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			dis[nx][ny] = dis[cur.X][cur.Y] + 1;
			vis[nx][ny] = true;
			q.push({ nx,ny });
		}
	}
}

void check_runner() {
	int count = 1;
	pair <int, int> cur =  chaser;
	while (true) {
		if (board[cur.X][cur.Y] > 0) {

			score += board[cur.X][cur.Y] * t;
			board[cur.X][cur.Y] = 0;
			for (int i = 0; i <= M; i++) {
				if (runners[i].x == cur.X && runners[i].y == cur.Y && !runners[i].out)
					runners[i].out = true;
			}
		}
		cur.X = cur.X + dx[c_dir];
		cur.Y = cur.Y + dy[c_dir];
		if (cur.X < 0 || cur.X >= N || cur.Y < 0 || cur.Y >= N) return;
		if(count == 3) return;
		count++;
	}
}

int main() {
	cin >> N >> M >> H >> K;

	runners.push_back({ 0,0,0,0,true });
	int x, y, d;
	for (int i = 1; i <= M; i++) {
		cin >> x >> y >> d;
		runners.push_back({ i,x-1,y-1,d,false });
		board[x -1][y-1] = 1;
	}
	for (int i = 0; i < H; i++) {
		cin >> x >> y;
		board[x-1][y-1] = -1;
	}
	t = 1;
	c_dir = 0;
	int change = 1;
	bool go = true;
	bool back = false;
	bool first = false;
	chaser = { N / 2 , N / 2 }; //술래 좌표
	while (true) {
		if(go) {
			for (int i = 0; i < change; i++) {
				if (t == K + 1) {
					cout << score;
					return 0;
				}
				BFS();
				for (int j = 1; j <= M; j++) {
					if (!runners[j].out)
						runner_move(runners[j]);
				}
				chaser.X = chaser.X + dx[c_dir];
				chaser.Y = chaser.Y + dy[c_dir]; //바로 움직임
				if (chaser.X == 0 && chaser.Y == 0) {
					c_dir = 2;
					check_runner();
					back = true;
					go = false;
					change = N-1;
					first = false;
					t++;
					break;
				}

				if (i == change - 1)
					c_dir = (c_dir + 1) % 4; //도착하자마자 방향바뀜.

				check_runner();
				t++;
			}
			if (c_dir == 2 || c_dir == 0)
			{
				if(!back)
				change++;
			}
		}
		if (back) {
			for (int i = 0; i < change; i++) {
				if (t == K + 1) {
					cout << score;
					return 0;
				}
				BFS();
				for (int j = 1; j <= M; j++) {
					if (!runners[j].out)
						runner_move(runners[j]);
				}
				chaser.X = chaser.X + dx[c_dir];
				chaser.Y = chaser.Y + dy[c_dir]; //바로 움직임

				if (chaser.X == N / 2 && chaser.Y == N / 2) {
					c_dir = 0;
					check_runner();
					back = false;
					go = true;
					change = 1;
					first = false;
					t++;
					break;
				}
				if (i == change - 1)
				{
					c_dir = (c_dir - 1);
					if(c_dir < 0) c_dir = 3;
				}

				check_runner();
				t++;
			}
			if ((c_dir == 3 || c_dir == 1) && !go)
			{
				if(first) change--;
				first = true;
			}
		}
	}
}