문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek/description?page=1&pageSize=20
💻 문제 풀이 : C++
// 술래 움직임을 어떻게 할까...?
// 도망자 최대 만명이므로 계속 탐색 불가능
// 나무지도와 도망자 지도를 만들고 갱신하자!
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAP_SIZE 101
using namespace std;
struct Coord {
int r, c, d;
};
int n, m, h, k;
Coord catcher;
int tree[MAP_SIZE][MAP_SIZE];
// 방향만 기록해도 됨!
// 현재 턴에서 도망자의 좌표
vector<int> now_r[MAP_SIZE][MAP_SIZE];
// 다음 턴에서 도망자의 좌표
vector<int> next_r[MAP_SIZE][MAP_SIZE];
// 정방향 술래 방향
int catcher_dir[MAP_SIZE][MAP_SIZE];
// 역방향 술래 방향
int catcher_dir_rev[MAP_SIZE][MAP_SIZE];
// 방향 플래그
int flagDir;
int answer;
// 좌, 우 ,상, 하
int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };
// 시계방향 돌리기
int turnRight(int d)
{
// 좌 -> 상
if (d == 0) return 2;
// 우 -> 하
else if (d == 1) return 3;
// 상 -> 우
else if (d == 2) return 1;
// 하 -> 좌
else if (d == 3) return 0;
}
int inRange(int r, int c)
{
if (r <= 0 || c <= 0 || r > n || c > n) return 0;
else return 1;
}
int getAbs(int a)
{
return a > 0 ? a : a * (-1);
}
int getDist(int r1, int c1, int r2, int c2)
{
return getAbs(r1 - r2) + getAbs(c1 - c2);
}
int turnBack(int d)
{
if (d == 0) return 1;
else if (d == 1) return 0;
else if (d == 2) return 3;
else if (d == 3) return 2;
}
void CLEAR()
{
memset(catcher_dir_rev, 0, sizeof(catcher_dir_rev));
memset(catcher_dir, 0, sizeof(catcher_dir));
memset(tree, 0, sizeof(tree));
answer = 0;
}
void makeCatcherMap()
{
int r = n / 2 + 1;
int c = n / 2 + 1;
// 술래는 위를 보고 시작
int d = 2;
catcher_dir[r][c] = 2;
// 1, 1, 2, 2, 3, 3, ...
int now_dir = 2;
// 방향전환 확인
int now_cnt = 1;
// r, c 모두 1이 아닐 때
while ((r - 1) || (c - 1))
{
for (int i = 0; i < now_cnt; i++)
{
catcher_dir[r][c] = now_dir;
r += dr[now_dir];
c += dc[now_dir];
catcher_dir_rev[r][c] = turnBack(now_dir);
// 이동하는 도중 (1, 1)에 도착하면 중지
if (r == 1 && c == 1)
{
break;
}
}
// 이동이 끝나면 전환
now_dir = turnRight(now_dir);
// 방향이 위/아래일때
if (now_dir >= 2)
{
now_cnt++;
}
}
}
void runnerMove()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 0; k < now_r[i][j].size(); k++)
{
// 거리가 3 이하만 이동
int dist = getDist(i, j, catcher.r, catcher.c);
// ## 오답노트 체크!!
// 거리가 3보다 멀면 이동 X
if (dist > 3)
{
next_r[i][j].push_back(now_r[i][j][k]);
continue;
}
int nr = i + dr[now_r[i][j][k]];
int nc = j + dc[now_r[i][j][k]];
// 움직이려는 칸에 술래가 있으면 이동 X
if (nr == catcher.r && nc == catcher.c)
{
next_r[i][j].push_back(now_r[i][j][k]);
continue;
}
// 격자를 벗어나는 경우
if (!inRange(nr, nc))
{
// 방향을 반대로
now_r[i][j][k] = turnBack(now_r[i][j][k]);
nr = i + dr[now_r[i][j][k]];
nc = j + dc[now_r[i][j][k]];
// 술래가 있다면 이동 X
if (nr == catcher.r && nc == catcher.c)
{
next_r[i][j].push_back(now_r[i][j][k]);
continue;
}
// 다음 턴 도망자 좌표 최신화
next_r[nr][nc].push_back(now_r[i][j][k]);
}
else
{
// 모두 아니면 이동
next_r[nr][nc].push_back(now_r[i][j][k]);
}
}
}
}
// next -> now
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
now_r[i][j] = next_r[i][j];
next_r[i][j].clear();
}
}
}
void catcherMove()
{
int r = catcher.r;
int c = catcher.c;
// 정방향일 때
if (flagDir == 0)
{
// 술래 한 칸 이동
catcher.r += dr[catcher_dir[r][c]];
catcher.c += dc[catcher_dir[r][c]];
catcher.d = catcher_dir[catcher.r][catcher.c];
// ## 오답노트 !!
// (1,1)에 도달하면
if (catcher.r == 1 && catcher.c == 1)
{
flagDir = 1;
}
}
// 역방향일 때
else
{
// 술래 한 칸 이동
catcher.r += dr[catcher_dir_rev[r][c]];
catcher.c += dc[catcher_dir_rev[r][c]];
catcher.d = catcher_dir_rev[catcher.r][catcher.c];
// 가운데에 도착하면
if (catcher.r == n / 2 + 1 && catcher.c == n / 2 + 1)
{
flagDir = 0;
}
}
}
void INPUT()
{
cin >> n >> m >> h >> k;
// 술래는 위를 보고 시작
catcher = {(n/2 + 1), (n/2 + 1), 0};
// 방향 정하기
makeCatcherMap();
for (int i = 0; i < m; i++)
{
int x, y, d;
cin >> x >> y >> d;
// 좌우로 움직이면 오른쪽을 보고 시작
if (d <= 1)
now_r[x][y].push_back({ 1 });
// 상하로 움직이면 아래를 보고 시작
else
now_r[x][y].push_back({ 3 });
}
for (int i = 0; i < h; i++)
{
int x, y;
cin >> x >> y;
tree[x][y] = 1;
}
}
void doCatch(int turn)
{
int d = catcher.d;
// 시야는 3칸
for (int i = 0; i < 3; i++)
{
int r = catcher.r + i * dr[d];
int c = catcher.c + i * dc[d];
if (!inRange(r, c)) continue;
// 나무가 있으면 건너뛰기
if (tree[r][c]) continue;
if (now_r[r][c].empty()) continue;
answer += turn * now_r[r][c].size();
now_r[r][c].clear();
}
}
void SOLVE()
{
int t = 1;
while (t <= k)
{
// 도망자 움직이기
runnerMove();
// 술래 움직이기
catcherMove();
// 도망자 잡기
doCatch(t);
t++;
}
cout << answer << endl;
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
} 📌 memo 😊
좌표를 구조체로 만들어서 다룰 때 최신화하기!
int r = Coord a.row;
int c = Coord a.col;
r += dr[d];
c += dc[d];위와 같이 코드를 작성하면 바뀌는 것은 지역변수 r,c이다.
따라서 바뀐 좌표를 "실제로" 반영시키려면
1. 가독성이 떨어져도 구조체의 멤버를 직접 연산한다.
2. 바뀐 좌표를 다시 구조체의 멤버에 대입한다. 예를들면,
a.row = r;
a.col = c;와 같은 부분을 추가해야 한다.
now 맵과 next 맵을 만들 때, 모든 now가 모든 next에 대응되는지 확인해야 한다.
초기에 위에 문제에서, 움직이지 않는 now는 next로 대응시키지 않고 continue 처리를 해주었다.
따라서 next가 저절로 작아져 worst case에서 값이 대부분 0으로 나오게 되는 문제가 발생했다.
현재 좌표에서 "바로" 원하는 값을 얻을 수 있어야 한다.
예를 들어
1. 현재 좌표에서 다음 좌표로 갈 때 최단 경로로 가야한다.
2. 현재 좌표에서 다음 좌표로 갈 때 정해진 방향으로 가야한다.
... 등의 경우가 있다.
그런 경우 "정답맵"을 만들어서 문제 풀이에 활용해야 한다. 마치 silver bullet 지도를 만든다고 생각하면 되는데, 단점은 머리가 아프다😂) 그러나 대부분 이것이 문제의 핵심이므로, 정답맵을 올바르게 만들기만 하면 문제의 풀이가 한결 쉬워진다.
이 문제의 경우에는
void makeCatcherMap()
{
int r = n / 2 + 1;
int c = n / 2 + 1;
// 술래는 위를 보고 시작
int d = 2;
catcher_dir[r][c] = 2;
// 1, 1, 2, 2, 3, 3, ...
int now_dir = 2;
// 방향전환 확인
int now_cnt = 1;
// r, c 모두 1이 아닐 때
while ((r - 1) || (c - 1))
{
for (int i = 0; i < now_cnt; i++)
{
catcher_dir[r][c] = now_dir;
r += dr[now_dir];
c += dc[now_dir];
catcher_dir_rev[r][c] = turnBack(now_dir);
// 이동하는 도중 (1, 1)에 도착하면 중지
if (r == 1 && c == 1)
{
break;
}
}
// 이동이 끝나면 전환
now_dir = turnRight(now_dir);
// 방향이 위/아래일때
if (now_dir >= 2)
{
now_cnt++;
}
}
}함수를 통해 현재 좌표에서 "술래가 어디로 가야할지"를 가리키는 catcher_dir, catcher_dir_rev를 미리 작성하였다. (코드트리의 정답 참고)
공부방