5 DERECHA
삼성 SW 역량테스트 2023 하반기 오후 1번 문제 - 루돌프의 반란 (Youtube 영상풀이) 본문
[문제 유형]
(주) Simulation
=> (DFS) + Simulation(job scheduler 관리(Queue or Array) + 2차원 map + (Sort)
(부) 2구조체 배열 + 2 scheduling
[문제 접근]
Simulation 문제고 그 중에서도 job scheduler를 관리하는 문제이며 역시나 2차원 map에서 움직이는 유형입니다. 그리고 job scheduler 과정에서 recursive 함수가 포함되는 것까지 기존에 출제되던 유형입니다. 이번에는 Queue가 아닌 Array로 관리할 수 있게 나왔습니다. 다음에는 Queue를 이용해서 문제가 나올수 있겠네요. 아래는 해당 문제를 Note에 적어가며 정리하면서 접근해가는 과정의 일입니다.
1) 문제를 읽어보면서 제일 처음에 구조체를 어떤식으로 만들지 생각해봐야 합니다. 루돌프 구조체 하나, 산타 구조체 배열을 만들고자 합니다.
-> 각 구조체마다 어떤 것들을 넣으면 좋을지 문제를 읽고 더해야합니다. 루돌프는 좌표만 나타내도 충분할 것 같지만, 산타는 좌표뿐만이 아니라 기절했는지, 죽었는지, 점수는 몇 점인지가 더 필요할 것 같네요.
-> 필요한 자료구조는 결론적으로 아래와 같다고 생각했습니다.
2) 아래는 문제에서 한글로 적힌 것을 본인이 이해하기 쉬운 방식으로 노트정리를 하는 과정의 일부입니다.
3) Simulation을 진행할 알고리즘을 생각하고, main문을 작성하고, 함수에서 어떤 기능을 할지 디자인 합니다. 시간복잡도와 공간복잡도를 계산합니다.
job schdeuling 관련 simulation인데 queue를 이용하지 않고, array로 만들어서 동작하려고 합니다.
2D map이동이니까 dr, dc가 필요합니다.
main문은 아래와 같이 하려고 합니다.
시간 복잡도는 최악의 상황에 게임턴수 x (산타의 수) 이라고 계산했습니다 (O(n) = M x P). 산타의 움직임마다 상호작용이 생겨서 모든 산타가 계속 움직인다고 가정했을때도 어림잡아도 O(n) = M x P^2이기에 충분한 시간복잡도입니다.
전반적인 함수는 다음과 같이 작성하려고 합니다.
[주의 사항]
1) 산타의 idx가 testcase에 주어져서 나오는데 1번부터 시작됩니다. 그리고 map을 보통 0으로 초기화하고, map에다가 산타의 idx를 적으려고 하기 때문에, 이런 경우에는 산타의 idx를 0부터 시작하기 보다는, 문제에서 주어진대로 1부터 시작하는 것이 좋습니다.
2) 거리를 구할때는 항상 위에서 주어진 공식을 사용해야합니다((r1 - r2)^2 + (c1 - c2)^2). 같은 거리 차이인 것 같아보여도 막상 좌표가 바뀌면서 거리가 바뀝니다.
아래는 해당 공식을 사용 안 했을때 나오는 결과입니다.
5 10 5 1 2
5 5
2 1 4
1 3 2
4 2 4
5 1 3
3 5 3
정답 : 8 14 15 12 12
오답 : 8 12 15 13 13
3) 상호작용하는 recursive함수를 조심해야합니다. 항상 Simulation 문제에는 recursive함수가 나오고, 해당 함수에서 까다로운 testcase를 발생시킵니다. 그러기에 recursive함수를 조심해야합니다. 이번에는 산타가 부딪히면서 밀려나는 과정에서 산타의 idx를 알맞게 지워주고, 구조체에 알맞게 넣어주는 것이 중요했습니다.
4) 산타가 map 밖으로 나간 경우에는 map밖의 위치에 산타의 idx를 넣으면 안 됩니다. stack메모리를 사용하기에 원하지 않은 부분의 메모리 값을 바꿀 수 있습니다.
아래는 stack메모리를 덮어쳤을때 나오는 결과입니다.
50 500 20 1 4
5 5
1 10 38
14 21 48
8 40 49
12 10 33
4 16 41
16 34 22
17 47 44
18 25 26
6 3 18
9 36 22
10 3 43
11 18 46
15 49 28
7 23 12
13 50 15
19 6 32
3 12 30
20 3 3
2 49 5
5 6 5
정답 : 94 43 114 193 89 120 104 102 175 101 92 104 134 120 221 283 88 186 97 190
오답 : 94 43 114 141 89 103 320 438 288 234 92 104 134 425 575 175 88 333 97 197
[코드]
#include <iostream>
#include <string.h>
#include <limits.h>
int N, M, P, C, D;
int mapp[51][51];
int sdr[] = { -1, 0 , 1, 0 };
int sdc[] = { 0, 1, 0, -1 };
int rdr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int rdc[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
struct Ru {
int r, c;
}ru;
struct San {
int r, c, ko, dead, score;
}san[31];
void print() {
for (int i = 0; i < P; i++) {
printf("%d ", san[i].score);
}
printf("\n");
}
void input() {
scanf("%d %d %d %d %d", &N, &M, &P, &C, &D);
scanf("%d %d", &ru.r, &ru.c);
int r, c;
for (int i = 0, num = 0; i < P; i++) {
scanf("%d %d %d", &num, &r, &c);
san[num - 1].r = r;
san[num - 1].c = c;
}
}
void init() {
memset(mapp, 0, 51 * 51);
mapp[ru.r][ru.c] = -1;
for (int i = 0; i <= P; i++) {
mapp[san[i].r][san[i].c] = i + 1;
san[i].dead = 0;
san[i].ko = 0;
san[i].score = 0;
}
}
int select_rdir(int r1, int c1, int r2, int c2) {
int dir = 0;
int min_dis = (r2 - (r1 + rdr[0])) * (r2 - (r1 + rdr[0])) + (c2 - (c1 + rdc[0])) * (c2 - (c1 + rdc[0]));
for (int i = 1; i < 8; i++) {
int nr = r1 + rdr[i];
int nc = c1 + rdc[i];
if (nr <= 0 || nr > N || nc <= 0 || nc > N)
continue;
int distance = ((r2 - nr) * (r2 - nr)) + ((c2 - nc) * (c2 - nc));
if (min_dis > distance) {
min_dis = distance;
dir = i;
}
}
return dir;
}
int select_sdir(int r1, int c1, int r2, int c2) {
int min_dis = (r2 - r1) * (r2 - r1) + (c2 - c1) * (c2 - c1);
int dir = -1;
for (int i = 0; i < 4; i++) {
int nr = r1 + sdr[i];
int nc = c1 + sdc[i];
if (nr <= 0 || nr > N || nc <= 0 || nc > N)
continue;
if (mapp[nr][nc] > 0) // 중요표시가 지문에도 되어있음
continue;
int distance = ((r2 - nr) * (r2 - nr)) + ((c2 - nc) * (c2 - nc));
if (min_dis > distance) {
min_dis = distance;
dir = i;
}
}
return dir;
}
void second_move(int dr, int dc, int r, int c) {
int origin_santa = mapp[r][c] - 1;
int nr = r + dr;
int nc = c + dc;
san[origin_santa].r = nr;
san[origin_santa].c = nc;
if (nr > N || nr <= 0 || nc > N || nc <= 0) {
san[origin_santa].dead = 1;
return;
}
else if (mapp[nr][nc] > 0) {
second_move(dr, dc, nr, nc);
}
mapp[nr][nc] = origin_santa + 1;
}
void ru_move() {
int min_dis = INT_MAX, dir = 0;
San near_santa = san[0];
for (int i = 0; i < P; i++) {
if (san[i].dead) continue; // !!
int distance = (ru.r - san[i].r) * (ru.r - san[i].r) +
(ru.c - san[i].c) * (ru.c - san[i].c);
if (min_dis > distance || ((min_dis == distance) && (near_santa.r < san[i].r ||
((min_dis == distance) && near_santa.r == san[i].r && near_santa.c < san[i].c)))) { // !!
min_dis = distance;
near_santa.r = san[i].r;
near_santa.c = san[i].c;
dir = select_rdir(ru.r, ru.c, san[i].r, san[i].c);
}
}
mapp[ru.r][ru.c] = 0;
ru.r += rdr[dir];
ru.c += rdc[dir];
if (mapp[ru.r][ru.c] > 0) {
int idx = mapp[ru.r][ru.c] - 1;
san[idx].r += rdr[dir] * C; // rdr -> sdr !! sdr -> rdr !!
san[idx].c += rdc[dir] * C;
san[idx].score += C;
if (san[idx].r > N || san[idx].r <= 0 || san[idx].c > N || san[idx].c <= 0) {
san[idx].dead = 1;
}
else if (mapp[san[idx].r][san[idx].c] > 0) {
second_move(rdr[dir], rdc[dir], san[idx].r, san[idx].c);
mapp[san[idx].r][san[idx].c] = idx + 1;
}
else
mapp[san[idx].r][san[idx].c] = idx + 1;
san[idx].ko = 2; // 2- > 1 -> 2 수정
}
mapp[ru.r][ru.c] = -1;
}
void san_move() {
int dir;
for (int i = 0; i < P; i++) {
if (san[i].dead || san[i].ko)
continue;
dir = select_sdir(san[i].r, san[i].c, ru.r, ru.c);
if (dir == -1)
continue;
mapp[san[i].r][san[i].c] = 0;
san[i].r += sdr[dir];
san[i].c += sdc[dir];
if (san[i].r == ru.r && san[i].c == ru.c) {
dir = (dir + 2) % 4;
san[i].score += D;
san[i].r += sdr[dir] * D;
san[i].c += sdc[dir] * D;
san[i].ko = 2;
if (san[i].r >= 1 && san[i].r <= N && san[i].c >= 1 && san[i].c <= N) {
if (mapp[san[i].r][san[i].c] > 0) {
second_move(sdr[dir], sdc[dir], san[i].r, san[i].c);
}
}
}
if (san[i].r > N || san[i].r <= 0 || san[i].c > N || san[i].c <= 0) {
san[i].dead = 1;
}
else {
mapp[san[i].r][san[i].c] = i + 1;
}
}
}
void up_score(bool& finish) {
finish = true;
for (int i = 0; i < P; i++) {
if (san[i].dead == 0) {
finish = false;
san[i].score += 1;
if (san[i].ko > 0)
san[i].ko--;
}
}
}
int main() {
bool finish = false;
input();
init();
for (int i = 1; i <= M; i++) {
ru_move();
san_move();
up_score(finish);
if (finish)
break;
}
print();
return 0;
}
Youtube 풀이
https://www.youtube.com/watch?v=QIVn6r4kg5Y
안녕하세요.
삼성전자에서 2020년 3월부터 2024년 3월까지 4년 근무하고 퇴직하였습니다. 현재 본격적으로 코딩테스트 온라인 과외 수업을 진행합니다. Software Maestro 10기 였으며 공개 S/W대회 어플리케이션 부문 최우수상 수상 경력 있습니다.
삼성전자 근무시에 PRO 등급 취득하여 삼성전자 코딩테스트의 경우 2번 문제 풀이(PRO)에 큰 도움 드릴 수 있습니다. 또한 네카라쿠배나 LG, Hyundai 코딩테스트 대비도 가능하며, 현재 기업 맞춤형으로 대비해 드리고 있습니다.
관심있으신 분들은 문의 부탁드립니다.
아래는 제 링크드인 주소와 카카오톡 오픈 채팅 주소입니다.
Linkedin : https://www.linkedin.com/in/kaykim30/