안녕하세요.
오늘은 "플래티넘으로 가는 길" 두 번째 이야기로 찾아왔습니다. 이번에는 시뮬레이션 알고리즘 문제를 주제로 다뤄보려 합니다.
이번 글에서는 문제를 처음 접했을 때 어떻게 이해했는지, 어떤 방식으로 접근하여 해결했는지를 공유드리고자 합니다. 더불어, 시뮬레이션 알고리즘을 학습하며 느꼈던 점들도 함께 정리해보겠습니다.
시뮬레이션 알고리즘 문제는 백준을 포함한 여러 플랫폼에서 정말 다양하게 출제되고 있습니다. 처음에는 어떤 문제를 소개드리는 게 좋을지 꽤 고민했지만, 이 문제를 선택하게 된 데에는 몇 가지 이유가 있습니다.
물론, 이 외에도 훌륭한 시뮬레이션 문제가 많습니다. 만약 추천하고 싶은 문제가 있다면 댓글로 공유해 주세요. 함께 고민하고 성장할 수 있는 기회가 되면 좋겠습니다.
그럼, 이제 본격적으로 문제를 어떻게 해석하고 접근했는지, 그리고 어떤 방식으로 구현했는지 소개드리겠습니다.
1. 낚시왕은 1초에 한 칸씩 오른쪽으로 이동합니다. 열을 기준으로 1씩 증가하며 움직이게 됩니다.
2. 낚시왕이 위치한 열에서 가장 가까운 행에 있는 상어를 잡습니다. 잡은 상어는 사라지고, 그 상어의 무게가 총합 점수에 반영됩니다.
3. 모든 상어는 자신의 속력과 방향에 따라 이동합니다. 벽에 부딪힐 경우 방향을 반대로 바꾸며, 위치를 계속 갱신해 나갑니다.
4. 한 칸에 여러 마리의 상어가 도착할 수 있습니다. 이 경우 가장 무게가 큰 상어만 생존하고, 나머지 상어는 모두 사라집니다.
5. 낚시왕이 끝까지 이동할 때까지, 위의 1~4번 과정을 반복합니다.
문제를 해석하고 나면, 본격적으로 데이터를 어떻게 구조화할지, 그리고 시뮬레이션 로직을 어떤 방식으로 구현할지에 대한 고민이 필요했습니다.
저는 이 문제를 풀기 위해 다음과 같이 메모리 구조를 설계하고, 시뮬레이션 함수를 어떻게 구성할지 단계적으로 정리해 나갔습니다.
<출처: baekjoon 문제 17143번 그림>
풀이
전체 코드
#include <stdio.h>
#include <iostream>
#include <vector>
struct Sharks {
std::vector<int> speeds;
std::vector<int> directions;
std::vector<int> sizes;
void Init(int r, int c) {
int n = (r + 1) * (c + 1);
speeds.reserve(n);
speeds.resize(n);
directions.reserve(n);
directions.resize(n);
sizes.reserve(n);
sizes.resize(n);
}
};
// n = total Col
void InputSharks(int n, int m, struct Sharks& sharks) {
for ( int i = 0; i < m; i++ ) {
int r, c, s, d, z;
std::cin >> r >> c >> s >> d >> z;
getchar();
int k = r * n + c;
sharks.speeds[k] = s;
sharks.directions[k] = d;
sharks.sizes[k] = z;
}
}
class SimulationClass {
public:
SimulationClass(int r_, int c_, struct Sharks& sharks_) : r(r_), c(c_), sharks(sharks_) {
int n = (r + 1) * (c + 1);
speeds.reserve(n);
directions.reserve(n);
sizes.reserve(n);
}
void Start() {
int n = ( r + 1 ) * ( c + 1 );
int answer = 0;
for ( int i = 1; i < c + 1; i++ ) {
// init
speeds.clear();
speeds.resize(n);
directions.clear();
directions.resize(n);
sizes.clear();
sizes.resize(n);
// fishing
answer += Fishing(i);
// move
Move();
// copy
Copy();
}
std::cout << answer << std::endl;
}
private:
int r;
int c;
struct Sharks& sharks;
std::vector<int> speeds;
std::vector<int> directions;
std::vector<int> sizes;
int Fishing(const int targetCol) {
int size = 0;
for ( int i = 1; i < r + 1; i++ ) {
int n = i * ( c + 1) + targetCol;
if ( sharks.directions[n] == 0 ) continue;
size = sharks.sizes[n];
sharks.speeds[n] = 0;
sharks.directions[n] = 0;
sharks.sizes[n] = 0;
break;
}
return size;
}
// 1 -> pass
int CompareShark( int i, int j, int size ) {
int targetSize = sizes[i * (c + 1) + j];
if ( size > targetSize ) return 1;
else return 0;
}
void ChangeShark(int i, int j, int sharkSpeed, int sharkDirection, int sharkSize) {
int compare_bool = CompareShark(i, j, sharkSize);
if (compare_bool) {
int n = i * (c + 1) + j;
speeds[n] = sharkSpeed;
directions[n] = sharkDirection;
sizes[n] = sharkSize;
}
}
void Move() {
std::vector<int>& sharkSpeeds = sharks.speeds;
std::vector<int>& sharkDirections = sharks.directions;
std::vector<int>& sharkSizes = sharks.sizes;
for ( int i = 1; i < r + 1; i++ ) {
for ( int j = 1; j < c + 1; j++ ) {
int n = ( i * (c + 1)) + j;
if (sharkDirections[n] == 0) continue;
int current_i = i, current_j = j;
int sharkSpeed = sharkSpeeds[n], remindSpeed = sharkSpeeds[n];
int sharkDirection = sharkDirections[n], currentDirction = sharkDirections[n];
int sharkSize = sharkSizes[n];
// r
if ( sharkDirection == 1 || sharkDirection == 2 ) {
int stop = 1;
while (stop) {
if ( currentDirction == 1 ) {
if ( current_i > remindSpeed ) {
stop = 0;
current_i -= remindSpeed;
ChangeShark(current_i, current_j, sharkSpeed, currentDirction, sharkSize);
} else {
remindSpeed = remindSpeed - current_i + 1;
current_i = 1;
currentDirction = 2;
}
}
else {
int remainRow = r - current_i;
if ( remainRow >= remindSpeed ) {
stop = 0;
current_i += remindSpeed;
ChangeShark(current_i, current_j, sharkSpeed, currentDirction, sharkSize);
} else {
remindSpeed -= remainRow;
current_i = r;
currentDirction = 1;
}
}
}
}
// c
else {
int stop = 1;
while ( stop ) {
if (currentDirction == 3) {
int remain_j = c - current_j;
if ( remain_j >= remindSpeed ) {
stop = 0;
current_j += remindSpeed;
ChangeShark(current_i, current_j, sharkSpeed, currentDirction, sharkSize);
} else {
remindSpeed -= remain_j;
current_j = c;
currentDirction = 4;
}
} else {
if ( current_j > remindSpeed ) {
stop = 0;
current_j -= remindSpeed;
ChangeShark(current_i, current_j, sharkSpeed, currentDirction, sharkSize);
} else {
remindSpeed = remindSpeed - current_j + 1;
current_j = 1;
currentDirction = 3;
}
}
}
}
}
}
}
void Copy() {
for ( int i = 1; i < r + 1; i++ ) {
for ( int j = 1; j < c + 1; j++ ) {
int n = i * (c + 1) + j;
sharks.speeds[n] = speeds[n];
sharks.directions[n] = directions[n];
sharks.sizes[n] = sizes[n];
}
}
}
};
int main(void) {
// r, c, m
int r, c, m;
std::cin >> r >> c >> m;
getchar();
// sharks
struct Sharks sharks;
sharks.Init(r, c);
InputSharks(c + 1, m, sharks);
// class
SimulationClass sc(r, c, sharks);
sc.Start();
return 0;
}
🦈 상어 정보 메모리 구조
struct Sharks {
std::vector<int> speeds;
std::vector<int> directions;
std::vector<int> sizes;
void Init(int r, int c) {
int n = (r + 1) * (c + 1);
speeds.reserve(n);
speeds.resize(n);
directions.reserve(n);
directions.resize(n);
sizes.reserve(n);
sizes.resize(n);
}
};
낚시왕 문제에서는 각 상어가 속도, 방향, 크기 세 가지 정보를 가지고 있으며, 이 정보를 상어의 위치에 맞게 저장할 필요가 있습니다. 처음에는 배열 형태를 고민했지만, 상어의 수가 유동적이라는 점에서 vector가 더 적합하다고 판단했습니다.
그리고 각 상어의 정보마다 별도의 vector를 만들어 struct로 묶어 관리하였습니다. 이렇게 하면 특정 정보만 갱신할 때 실수를 줄일 수 있고, 전반적인 메모리 관리도 안정적으로 할 수 있습니다.
🎣 시뮬레이션 메인 로직
void Start() {
int n = ( r + 1 ) * ( c + 1 );
int answer = 0;
for ( int i = 1; i < c + 1; i++ ) {
// init
speeds.clear();
speeds.resize(n);
directions.clear();
directions.resize(n);
sizes.clear();
sizes.resize(n);
// fishing
answer += Fishing(i);
// move
Move();
// copy
Copy();
}
std::cout << answer << std::endl;
}
낚시왕은 한 칸씩 오른쪽으로 이동하며, 시뮬레이션은 열 기준으로 반복됩니다. 이 반복문 안에서 총 3개의 핵심 동작이 수행됩니다:
-
Fishing – 해당 열에서 가장 위에 있는 상어를 잡고 점수를 누적
-
Move – 모든 상어들이 자신이 가진 속도, 방향에 따라 이동
-
Copy – 복사본 벡터에 저장된 상어 정보를 원본 구조에 반영
🧭 시뮬레이션 핵심: 상어 이동 함수
void Move() {
std::vector<int>& sharkSpeeds = sharks.speeds;
std::vector<int>& sharkDirections = sharks.directions;
std::vector<int>& sharkSizes = sharks.sizes;
for ( int i = 1; i < r + 1; i++ ) {
for ( int j = 1; j < c + 1; j++ ) {
int n = ( i * (c + 1)) + j;
if (sharkDirections[n] == 0) continue;
int current_i = i, current_j = j;
int sharkSpeed = sharkSpeeds[n], remindSpeed = sharkSpeeds[n];
int sharkDirection = sharkDirections[n], currentDirction = sharkDirections[n];
int sharkSize = sharkSizes[n];
// r
if ( sharkDirection == 1 || sharkDirection == 2 ) {
int stop = 1;
while (stop) {
if ( currentDirction == 1 ) {
if ( current_i > remindSpeed ) {
stop = 0;
current_i -= remindSpeed;
ChangeShark(current_i, current_j, sharkSpeed, currentDirction, sharkSize);
} else {
remindSpeed = remindSpeed - current_i + 1;
current_i = 1;
currentDirction = 2;
}
}
else {
int remainRow = r - current_i;
if ( remainRow >= remindSpeed ) {
stop = 0;
current_i += remindSpeed;
ChangeShark(current_i, current_j, sharkSpeed, currentDirction, sharkSize);
} else {
remindSpeed -= remainRow;
current_i = r;
currentDirction = 1;
}
}
}
}
// c
else {
int stop = 1;
while ( stop ) {
if (currentDirction == 3) {
int remain_j = c - current_j;
if ( remain_j >= remindSpeed ) {
stop = 0;
current_j += remindSpeed;
ChangeShark(current_i, current_j, sharkSpeed, currentDirction, sharkSize);
} else {
remindSpeed -= remain_j;
current_j = c;
currentDirction = 4;
}
} else {
if ( current_j > remindSpeed ) {
stop = 0;
current_j -= remindSpeed;
ChangeShark(current_i, current_j, sharkSpeed, currentDirction, sharkSize);
} else {
remindSpeed = remindSpeed - current_j + 1;
current_j = 1;
currentDirction = 3;
}
}
}
}
}
}
}
이 문제에서 가장 핵심이 되는 부분은 상어의 이동입니다. 시뮬레이션 알고리즘에서는 문제의 흐름과 규칙을 정확하게 이해하고, 그것을 코드로 옮기는 과정이 가장 중요합니다.
방향 처리
-
1, 2번: 상하 이동 → 행 값을 변경
-
3, 4번: 좌우 이동 → 열 값을 변경
이렇게 방향에 따라 조건을 나누어 처리했습니다. 특히 상어가 벽에 부딪히면 방향을 반대로 바꿔야 하는 부분은 생각보다 까다로웠습니다.
저는 남은 이동 거리(remindSpeed)와 현재 위치를 비교하며 조건 분기를 통해 방향을 조정했습니다.
메모리 처리 전략
여기서 중요한 고민이 있었습니다.
"기존 배열(원판)을 직접 갱신할까? 아니면 복사본을 만들어서 처리할까?"
보통은 메모리를 아끼기 위해 원본을 바로 수정하지만, 이 문제의 경우에는 상어가 서로 잡아먹는 순서나 같은 위치에 여러 상어가 동시에 도달하는 경우가 있어, 안정성을 위해 복사본 벡터에 먼저 저장하고 마지막에 한 번에 반영하는 구조로 구현했습니다.
2차원 → 1차원 인덱스 처리
배열을 1차원 vector로 관리하기 때문에, 상어가 도착한 위치는 다음과 같이 계산했습니다:
그리고 해당 위치에 ChangeShark 함수를 통해 상어 정보를 저장하도록 했습니다. 이 함수는 이미 저장된 상어와 비교하여, 더 큰 상어만 살아남도록 처리합니다.
💡 마무리 정리
이 문제는 단순한 구현을 넘어서, 시뮬레이션 알고리즘의 본질인 상태 변화 관리와 충돌 처리, 그리고 자료구조 설계까지 종합적으로 고민하게 만드는 좋은 문제였습니다.
저는 구현하기 전에 흐름을 확실히 정리하고, 각 단계를 함수 단위로 명확히 분리하며 구현했습니다. 특히 상어 이동 로직에서 방향 전환, 거리 계산, 경계 조건 처리는 직접 손으로 흐름을 그려보며 코드를 짜는 것이 매우 도움이 되었습니다.
결론
이번 문제 외에도 여러 시뮬레이션 알고리즘 문제들을 풀어보면서 느낀 점이 많았습니다.
특히 이 유형의 문제는 단순히 구현만 잘해서 되는 것이 아니라, 요구사항을 정확히 파악하고, 상황을 설계한 뒤, 그 흐름을 논리적으로 코드에 녹여내는 과정을 요구합니다.
이는 마치 실제로 개발자가 사용자 혹은 의뢰자의 요구를 받아 기능을 설계하고 구현하는 과정과도 매우 흡사합니다.
그런 점에서 시뮬레이션 알고리즘은 문제 해결 능력뿐만 아니라 개발자로서 가져야 할 사고방식을 기를 수 있는 매우 좋은 훈련 도구라고 느꼈습니다.
다음 포스팅에서는 브루트포스(완전 탐색) 알고리즘 문제들을 다뤄볼 예정입니다. 어떤 문제들을 만나게 될지 벌써부터 기대가 됩니다.
긴 글 읽어주셔서 감사드리며, 다음 포스팅에서 다시 뵙겠습니다.
모두들 공부와 개발, 그리고 도전하는 모든 일들에 좋은 결과 있으시길 바랍니다.
화이팅!
