문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20
💻 문제 풀이 : C++
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
struct Coord {
int r, c;
};
int n, m;
int MAP[20][20];
// 해당 베이스캠프/편의점에 도착했는지 확인
int Arrv[20][20];
// 모든 사람의 이동이 끝난 다음에 반영
int nextArrv[20][20];
// 해당 편의점이 정해졌는지(불가능한지) 기록
int Picked[20][20];
// BFS 방문기록
int visited[20][20];
// 도착점까지의 방향을 기록
int dirt[20][20];
// 편의점
vector<Coord> cs;
// 사람이 격자(부트캠프)에 위치했는지 기록
int started[35];
// 사람이 편의점에 도착했는지 기록
int arrived[35];
// 사람의 현재 위치 기록
Coord person[35];
// ↑, ←, →, ↓
int dr[] = { -1, 0, 0, 1 };
int dc[] = { 0, -1, 1, 0 };
int turnBack(int dir)
{
if (dir == 0) return 3;
else if (dir == 1) return 2;
else if (dir == 2) return 1;
else if (dir == 3) return 0;
}
int isAllArrive()
{
for (int i = 0; i < m; i++)
{
if (arrived[i] == 0) return 0;
}
return 1;
}
int inRange(int r, int c)
{
if (r < 0 || c < 0 || r >= n || c >= n) return 0;
else return 1;
}
void move(int idx)
{
int flagEnd = 0;
// BFS로 길 찾기
queue<Coord> nowQ;
nowQ.push(person[idx]);
visited[person[idx].r][person[idx].c] = 1;
while (!nowQ.empty())
{
Coord now = nowQ.front();
nowQ.pop();
for (int i = 0; i < 4; i++)
{
Coord next = {now.r + dr[i], now.c + dc[i]};
if (!inRange(next.r, next.c)) continue;
if (Arrv[next.r][next.c] != 0) continue;
if (visited[next.r][next.c] != 0) continue;
// 편의점에 도착하면
if (next.r == cs[idx].r && next.c == cs[idx].c)
{
visited[next.r][next.c] = visited[now.r][now.c] + 1;
dirt[next.r][next.c] = turnBack(i);
flagEnd = 1;
break;
}
visited[next.r][next.c] = visited[now.r][now.c] + 1;
dirt[next.r][next.c] = turnBack(i);
nowQ.push(next);
}
// 찾았으면 탐색 종료하기
if (flagEnd == 1) break;
}
// 방문 기록을 초기화하고
memset(visited, 0, sizeof(visited));
// 편의점부터 출발한 지점까지 역으로 추적하기
int tmpR = cs[idx].r;
int tmpC = cs[idx].c;
visited[tmpR][tmpC] = 1;
// 편의점에서 역으로 출발지점에 도착하면 탐색 종료
while (!(tmpR == person[idx].r && tmpC == person[idx].c))
{
int nr = tmpR + dr[dirt[tmpR][tmpC]];
int nc = tmpC + dc[dirt[tmpR][tmpC]];
if (!inRange(nr, nc)) continue;
visited[nr][nc] = 1;
tmpR = nr;
tmpC = nc;
}
// 출발지점에서 가야하는 방향으로 1칸만 이동하기
for (int i = 0; i < 4; i++)
{
tmpR = person[idx].r + dr[i];
tmpC = person[idx].c + dc[i];
if (!inRange(tmpR, tmpC)) continue;
if (Arrv[tmpR][tmpC] != 0) continue;
if (visited[tmpR][tmpC] == 0) continue;
// 결과 반영하기
person[idx].r = tmpR;
person[idx].c = tmpC;
break;
}
// 편의점에서 도착 완료한 경우
if (person[idx].r == cs[idx].r && person[idx].c == cs[idx].c)
{
nextArrv[person[idx].r][person[idx].c] = 1;
arrived[idx] = 1;
}
}
// 편의점에서 출발해서 역으로 베이스캠프 찾기
void setBasecamp(Coord s, int idx)
{
queue<Coord> nowQ;
nowQ.push(s);
visited[s.r][s.c] = 1;
while (!nowQ.empty())
{
Coord now = nowQ.front();
nowQ.pop();
for (int i = 0; i < 4; i++)
{
Coord next = { now.r + dr[i], now.c + dc[i] };
if (!inRange(next.r, next.c)) continue;
if (visited[next.r][next.c] != 0) continue;
if (Arrv[next.r][next.c] != 0) continue;
if (Picked[next.r][next.c] != 0) continue;
// 베이스캠프 발견하면
if (MAP[next.r][next.c] != 0) {
person[idx] = { next.r, next.c };
Picked[next.r][next.c] = 1;
return;
}
visited[next.r][next.c] = visited[now.r][now.c] + 1;
nowQ.push(next);
}
}
}
void CLEAR()
{
memset(Arrv, 0, sizeof(Arrv));
}
void INPUT()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> MAP[i][j];
}
}
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
cs.push_back({ x-1, y-1 });
}
}
void SOLVE()
{
int time = 1;
while (time < 10000)
{
memcpy(nextArrv, Arrv, sizeof(Arrv));
// m명의 사람만큼 반복
for (int i = 0; i < m; i++)
{
// 도착했으면 건너뛰기
if (arrived[i]) continue;
// 격자에 위치하지 않으면 건너뛰기
if (!started[i]) continue;
memset(dirt, 0, sizeof(dirt));
memset(visited, 0, sizeof(visited));
move(i);
}
memcpy(Arrv, nextArrv, sizeof(nextArrv));
// 베이스캠프 정하기
for (int i = 0; i < m; i++)
{
// t > m 인 경우
if(time - 1 < i) continue;
// 아직 정하지 않은 경우만 실행
if (arrived[i] == 1 ||
started[i] == 1) continue;
memset(visited, 0, sizeof(visited));
setBasecamp(cs[i], i);
}
// 베이스캠프 들어가기
if (time - 1 < m)
{
started[time - 1] = 1;
Arrv[person[time - 1].r][person[time - 1].c] = 1;
}
// 모두 도착했는지 확인하기
if (isAllArrive()) break;
time++;
}
cout << time << endl;
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
}📌 memo 😊
최단거리로 이동하는 경우 BFS를 떠올리면 된다.
1. 출발지점에서부터 목표지점에 도착하기 전까지 visited를 통해 거리를 기록한다.
2. 이때, dirt를 통해 이동한 방향을 기록한다.
3. 목표지점에 도착하면 visited를 초기화하고, 목표지점에서 다시 탐색하여 되돌아간다.
4. 목표지점에서 출발지점으로 되돌아오면 최단경로 완성!
공부방