[PS] 코드트리: 코드트리 빵

코드트리 빵

1. ↑, ←, →, ↓ 의 "우선순위"로 움직이기
2. 가장 가까운 x가 여러 가지일 경우 행이 작은 x, 행이 같다면 열이 작은 x

이 두개가 매번 헷갈렸는데 이 문제에서 두 개 동시에 써보니 이젠 구분이 된다.
전자는 저 순서대로 bfs 하란 뜻이고, 후자는 정렬을 하라는 뜻이다.

한번에 ac되었다. 아싸

 

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, n) for (int i = 0; i < n; i++)
#define endl "\n"
#define pii pair<int, int>

#define iib(r, c) (0 <= r && r < N && 0 <= c && c < N)

int N, M, num_arrived = 0;
int MAP[15][15];
int dr[4] = { -1, +0, +0, +1 };
int dc[4] = { +0, -1, +1, +0 };

bool cmp(const tuple<int, int, int>&t1, const tuple<int, int, int>&t2) {
	int lv1, r1, c1, lv2, r2, c2;
	tie(lv1, r1, c1) = t1, tie(lv2, r2, c2) = t2;
	if (lv1 == lv2) {
		if (r1 == r2) {
			return c1 < c2;
		}
		return r1 < r2;
	}
	return lv1 < lv2;
}

struct Man {
	enum Status { none, moving, finished };
	pii pos{ -1, -1 }, target;
	Status status = none;
	Man(int r, int c) { target = make_pair(r, c); }
};
vector<Man> vman;

int main() {
	cin >> N >> M;
	FOR(i, N) FOR(j, N) cin >> MAP[i][j];
	FOR(i, M) {
		int r, c; cin >> r >> c; r -= 1, c -= 1;
		vman.emplace_back(r, c);
	}

	int cnt = 0;
	for (cnt; num_arrived < M; cnt++) {
		// 1. 이동
		for (auto& man : vman) {
			if (man.status != man.moving) continue;
			
			deque<tuple<vector<int>, int, int>> q;
            // 한 칸만 전진 해야해서 경로를 처음부터 하나씩 다 기록하기
			vector<int> _log;
			bool visited[15][15] = { false, };
			q.emplace_back(_log, man.pos.first, man.pos.second);
			while (!q.empty()) {
				vector<int> log; int r, c;
				tie(log, r, c) = q.front(); q.pop_front();

				if (visited[r][c]) continue;
				visited[r][c] = true;

				if (r == man.target.first && c == man.target.second) {
					_log = log;
					break;
				}

				FOR(i, 4) {
					int nr = r + dr[i], nc = c + dc[i];
					vector<int> new_log(log.begin(), log.end()); new_log.push_back(i);
					if (iib(nr, nc) && !visited[nr][nc] && MAP[nr][nc] != 9) q.emplace_back(new_log, nr, nc);
				}
			}

			// 로그의 첫 방향으로 전진
            int go_idx = _log.front();
			man.pos.first += dr[go_idx], man.pos.second += dc[go_idx];
		}

		// 2. 목적지 도착한 놈 있으면 벽 생성
		for (auto& man : vman) {
			if (man.status != man.moving) continue;
			if (man.pos.first == man.target.first && man.pos.second == man.target.second) {
				MAP[man.pos.first][man.pos.second] = 9;
				man.status = man.finished;
				num_arrived += 1;
			}
		}

		// 3. 투입
		if (cnt < M) {
			vector<tuple<int, int, int>> vt;
			deque<tuple<int, int, int>> q; q.emplace_back(0, vman[cnt].target.first, vman[cnt].target.second);
			bool visited[15][15] = { false, };
			while (!q.empty()) {
				int lv, r, c; tie(lv, r, c) = q.front(); q.pop_front();

				if (visited[r][c]) continue;
				visited[r][c] = true;

				if (MAP[r][c] == 1) {
					vt.emplace_back(lv, r, c);
					continue;
				}

				FOR(i, 4) {
					int nr = r + dr[i], nc = c + dc[i];
					if (iib(nr, nc) && !visited[nr][nc] && MAP[nr][nc] != 9) q.emplace_back(lv + 1, nr, nc);
				}
			}

			// 최소 경로인 애들 중 행이 작고, 열이 작은 순으로 정렬
            sort(vt.begin(), vt.end(), cmp);
			vman[cnt].pos = make_pair(get<1>(vt.front()), get<2>(vt.front()));
			MAP[get<1>(vt.front())][get<2>(vt.front())] = 9;
			vman[cnt].status = vman[cnt].moving;
		}
	}
	cout << cnt;
}