술래잡기 [2022-상반기 오전 1번 문제]
문제 링크
삼성 코딩테스트 기출 문제: 술래잡기 - 코드트리
주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.
문제 설명
n*n 격자에 술래는 정 중앙에 서 있음.
m명의 도망자가 있으며, 좌우 또는 상하로만 움직이는 유형이 있음. 좌우는 우부터 시작하고, 상하는 하부터 시작함.
h개의 나무가 있는데, 도망자와 겹칠 수 있음.
m명의 도망자가 움직이고 → 도망자가 움직이는 순임.
도망자와 술래가 거리가 3 이하라면 도망자가 움직임.
단, 바라보는 방향이 격자를 벗어나면 방향을 반대로 틀어줌. 그리고 다음 위치에 술래가 있다면 움직이지 않음.
술래는 달팽이 모양으로 움직임. 끝에 도달하면 거꾸로 움직임.
술래는 이동하고 나서 시야 안에 있는 도망자들을 잡음. 잡고 나면 턴*도망자 수 만큼의 점수를 획득함
총 획득한 점수를 출력하기.
해결 방법
시야 안에 있는 도망자들을 잡음.
void catch_runner(int t) {
int runner_map[101][101];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
memset(runner_map, 0, sizeof(runner_map));
for (int i = 0;i < runner.size();i++) {
if (runner[i].died) continue;
runner_map[runner[i].x][runner[i].y] = 1;
}
for (int i = 0;i < tree.size();i++) {
runner_map[tree[i].first][tree[i].second] = -1;
}
int cnt = 0;
int sight_x = sx;
int sight_y = sy;
for (int i = 0;i <= 2;i++) {
if (runner_map[sight_x][sight_y] == 1) {
for (int j = 0;j < runner.size();j++) {
if (runner[j].died) continue;
if (runner[j].x == sight_x && runner[j].y == sight_y) {
runner[j].died = true;
cnt++;
}
}
}
sight_x += dx[ss];
sight_y += dy[ss];
}
result += (cnt * t);
}
술래가 움직임
void tagger_move() {
int nc;
nc = sc + sd;
if (nc == 0) sd = 1;
if (nc == path.size()-1) sd = -1;
sx = path[nc].first, sy = path[nc].second;
sc = nc;
int tx, ty;
tx = path[nc + sd].first - sx, ty = path[nc + sd].second - sy;
if (tx == -1 && ty == 0) ss = 0;
else if (tx == 0 && ty == 1) ss = 1;
else if (tx == 1 && ty == 0) ss = 2;
else if (tx == 0 && ty == -1) ss = 3;
else {
cout << tx << " " << ty << "!\\n";
cout << "error?";
exit(0);
}
}
도망자들이 움직이게 함.
void runner_move() {
// 상,우,하,좌
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int rx, ry, rd, nx, ny;
for (int i = 0;i < runner.size();i++) {
if (runner[i].died) continue;
rx = runner[i].x, ry = runner[i].y, rd = runner[i].d;
if (abs(rx - sx) + abs(ry - sy) > 3) continue;
nx = rx + dx[rd], ny = ry + dy[rd];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
rd = (rd + 2) % 4;
nx = rx + dx[rd], ny = ry + dy[rd];
}
if (nx == sx && ny == sy) continue;
runner[i].x = nx, runner[i].y = ny, runner[i].d = rd;
}
}
술래 움직이는 방향 설정술래가 움직일 방향을 path 벡터에 넣어줌.
void init() {
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
memset(visited, 0, sizeof(visited));
queue<tuple<int, int,int>> que;
que.push({ 0,0,0});
path.push_back({ 0,0 });
visited[0][0] = 1;
int cx, cy,cd, nx, ny;
while (!que.empty()) {
tie(cx, cy,cd) = que.front();
que.pop();
nx = cx + dx[cd], ny = cy + dy[cd];
if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) {
cd = (cd + 1) % 4;
nx = cx + dx[cd], ny = cy + dy[cd];
}
path.push_back({ nx,ny });
if (nx == n / 2 && ny == n / 2) break;
visited[nx][ny] = 1;
que.push({ nx,ny,cd });
}
sx = n / 2, sy = n / 2;
sc = path.size() -1 , sd = -1;
}
전체 코드
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;
typedef struct {
int x, y, d;
bool died;
}_runner;
int n, m, h, k;
int visited[101][101];
vector<_runner> runner;
vector<pair<int, int>> tree;
vector<pair<int, int>> path;
int sx, sy,sc,sd,ss;
void input() {
cin >> n >> m >> h >> k;
int a,b,c;
for (int i = 0;i < m;i++) {
cin >> a >> b >> c;
_runner tmp;
tmp.x = a - 1, tmp.y = b - 1, tmp.d = c;
tmp.died = false;
runner.push_back(tmp);
}
for (int i = 0;i < h;i++) {
cin >> a >> b;
tree.push_back({ a-1,b-1 });
}
}
void init() {
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
memset(visited, 0, sizeof(visited));
queue<tuple<int, int,int>> que;
que.push({ 0,0,0});
path.push_back({ 0,0 });
visited[0][0] = 1;
int cx, cy,cd, nx, ny;
while (!que.empty()) {
tie(cx, cy,cd) = que.front();
que.pop();
nx = cx + dx[cd], ny = cy + dy[cd];
if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) {
cd = (cd + 1) % 4;
nx = cx + dx[cd], ny = cy + dy[cd];
}
path.push_back({ nx,ny });
if (nx == n / 2 && ny == n / 2) break;
visited[nx][ny] = 1;
que.push({ nx,ny,cd });
}
sx = n / 2, sy = n / 2;
sc = path.size() -1 , sd = -1;
}
void runner_move() {
// 상,우,하,좌
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int rx, ry, rd, nx, ny;
for (int i = 0;i < runner.size();i++) {
if (runner[i].died) continue;
rx = runner[i].x, ry = runner[i].y, rd = runner[i].d;
if (abs(rx - sx) + abs(ry - sy) > 3) continue;
nx = rx + dx[rd], ny = ry + dy[rd];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
rd = (rd + 2) % 4;
nx = rx + dx[rd], ny = ry + dy[rd];
}
if (nx == sx && ny == sy) continue;
runner[i].x = nx, runner[i].y = ny, runner[i].d = rd;
}
}
void tagger_move() {
int nc;
nc = sc + sd;
if (nc == 0) sd = 1;
if (nc == path.size()-1) sd = -1;
sx = path[nc].first, sy = path[nc].second;
sc = nc;
int tx, ty;
tx = path[nc + sd].first - sx, ty = path[nc + sd].second - sy;
if (tx == -1 && ty == 0) ss = 0;
else if (tx == 0 && ty == 1) ss = 1;
else if (tx == 1 && ty == 0) ss = 2;
else if (tx == 0 && ty == -1) ss = 3;
else {
cout << tx << " " << ty << "!\\n";
cout << "error?";
exit(0);
}
}
int result = 0;
void catch_runner(int t) {
int runner_map[101][101];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
memset(runner_map, 0, sizeof(runner_map));
for (int i = 0;i < runner.size();i++) {
if (runner[i].died) continue;
runner_map[runner[i].x][runner[i].y] = 1;
}
for (int i = 0;i < tree.size();i++) {
runner_map[tree[i].first][tree[i].second] = -1;
}
int cnt = 0;
int sight_x = sx;
int sight_y = sy;
for (int i = 0;i <= 2;i++) {
if (runner_map[sight_x][sight_y] == 1) {
for (int j = 0;j < runner.size();j++) {
if (runner[j].died) continue;
if (runner[j].x == sight_x && runner[j].y == sight_y) {
runner[j].died = true;
cnt++;
}
}
}
sight_x += dx[ss];
sight_y += dy[ss];
}
result += (cnt * t);
}
void solve(int t) {
runner_move();
tagger_move();
catch_runner(t);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("sample_input.txt", "r", stdin);
input();
init();
for (int i = 0;i < k;i++) {
solve(i + 1);
}
cout << result;
}