-
[PS] 코드트리: 코드트리 빵문제해결 2023. 10. 25. 17:23
- ↑, ←, →, ↓ 의 "우선순위"로 움직이기
- 가장 가까운 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; }
'문제해결' 카테고리의 다른 글
[PS] 코드트리: 왕실의 기사 대결 (0) 2023.10.25 [PS] 코드트리: 싸움땅 (0) 2023.10.25 [PS] 백준 1005번: ACM Craft (0) 2023.10.25 [PS] 백준 21610번: 마법사 상어와 비바라기 (0) 2023.10.25 [PS] 백준 10630번: RLE Replacement (0) 2023.10.25