#define _CRT_SECURE_NO_WARNINGS#include
//굳이 좌표값에 놓아줘야 하나??//낚시꾼이 어느 열에 왔을 때, 그 열에 있는 상어를 다 가져올 수 있다면?// 각 열에 해당하는 샤크리스트를 만들수 있다면? 그리고 그 리스트를 링크드List로 만들어낸다면?//2차원 LinkedList를 하나씩 떼어다가 붙여야 하겠지?typedef struct _tagShark {int x, y;int speed;int d;int size;_tagShark* next;_tagShark* prev;_tagShark() :x(0), y(0), speed(0), d(0), size(0), next(nullptr), prev(nullptr){}_tagShark(int x, int y, int speed, int d, int size):x(x), y(y), speed(speed), d(d), size(size), next(nullptr), prev(nullptr){}}SHARK, * pSHARK;SHARK* sharkList[101] = { nullptr };SHARK* endLine[101];SHARK sharks[10001];int N, X, Y;int currCount;SHARK* visit[101][101] = { nullptr };int total = 0;void separateNode(_tagShark* target, int index) {if (target->prev) {target->prev->next = target->next; //target의 next가 존재할 수도 있고, 아닐 수도 있지만 이 코드에는 문제가 없음}else {//target이 첫 노드일 때sharkList[index] = target->next;}//else {// sharkList[index] = target->next;// if (target->next) {// target->next->prev = nullptr;// }// else {// sharkList[index] = nullptr;// endLine[index] = nullptr;// }//}if (target->next) {target->next->prev = target->prev; //target의 prev가 존재할 수도 있고, 아닐 수도 있지만, 이 코드에는 문제가 없음}else {//target이 마지막 노드일 때endLine[index] = target->prev;}target->prev = nullptr;target->next = nullptr;if (!sharkList[index]) endLine[index] = nullptr;}void addNode(_tagShark* target, int index) {target->prev = nullptr;target->next = nullptr;if (!sharkList[index]) {sharkList[index] = target;endLine[index] = target;}else{//일반적인 경우endLine[index]->next = target;target->prev = endLine[index];endLine[index] = target;}}void removeNode(_tagShark* target) {//delete target;//target = nullptr;}void resetVisit(int X, int Y) {for (int i = 0; i <= Y; ++i)for (int j = 0; j <= X; ++j)visit[i][j] = nullptr;}int fishing(int index) {_tagShark* start = nullptr;_tagShark* target = nullptr;int y = Y + 10;if (sharkList[index]) {start = sharkList[index];}else {return 0;}while (start) {if (start->y < y) {y = start->y;target = start;}start = start->next;}if (target) {separateNode(target, index);return target->size;}return 0;}bool moveShark(_tagShark* target) {int cycle = 0;int serial = 0;int newIndex = 0;if (target->d < 3) {//위, 아래로 움직임 : Y값의 영향을 받음cycle = (Y - 1) * 2;}else {//오른쪽, 왼쪽으로 움직임 : X값의 영향을 받음cycle = (X - 1) * 2;}switch (target->d) {case 1: {//위serial = 2 * Y - target->y + 1 + target->speed;break;}case 2: {//아래serial = target->y + target->speed;break;}case 3: {//오른쪽serial = target->x + target->speed;break;}case 4: {//왼쪽serial = 2 * X - target->x + 1 + target->speed;break;}default: {break;}}if (target->d < 3) {newIndex = serial % cycle;if (newIndex >= Y) {target->d = 1;target->y = 2 * Y - newIndex;}else if (newIndex == 0) {target->d = 1;target->y = 2;}else {target->d = 2;target->y = newIndex;}}else {newIndex = serial % (2 * X - 2);if (newIndex >= X) {target->d = 4;target->x = 2 * X - newIndex;}else if (newIndex == 0) {target->d = 4;target->x = 2;}else {target->d = 3;target->x = newIndex;}}//----------target은 완전히 분리가 된 상태-----------------------if (!visit[target->y][target->x]) {visit[target->y][target->x] = target;return true;}else {if (visit[target->y][target->x]->size > target->size) {removeNode(target);return false;}else {separateNode(visit[target->y][target->x], visit[target->y][target->x]->x);removeNode(visit[target->y][target->x]);visit[target->y][target->x] = target;return true;}}}void moveAllShark() {_tagShark* target;_tagShark* next;bool result = false;for (int i = 1; i <= X; ++i) {if (sharkList[i]) {target = sharkList[i];while (target) {next = target->next;separateNode(target, i);result = moveShark(target);if (result) addNode(target, target->x);target = target->next;}}}}int main() {int y, x, s, d, size;scanf("%d %d %d", &Y, &X, &N);for (int i = 0; i < N; ++i) {scanf("%d %d %d %d %d", &y, &x, &s, &d, &size);sharks[i] = SHARK(x, y, s, d, size);addNode(&sharks[i], sharks[i].x);}for (int i = 1; i <= X; ++i) {total += fishing(i);resetVisit(X, Y);moveAllShark();}printf("%d\n", total);return 0;}이 코드의 문제점이 뭘까요? chat GPT보다 똑똑간 휴먼의 파워를 보여주세요ㅠㅠ
안녕하세요. 로디소프트 대표 임세원입니다.
문제의 조건이 많고 상어의 움직임, 충돌 처리 등 고려할 사항이 많아 구현이 까다로운 문제입니다. 코드를 살펴보니 연결리스트를 이용해 컬럼별로 상어를 관리하는 독창적인 아이디어를 사용하셨네요. 하지만 아쉽게도 몇가지 논리적 오류가 있어 정상적으로 동작하지 않을 겁니다.
ChatGPT와 같은 AI가 종종 복잡한 시뮬레이션 문제에서 논리적 허점을 찾지 못하는 경우가 있습니다. 코드의 핵심 로직과 자료구조의 상호작용을 깊이 있게 파악해야 하기 때문이죠. 코드를 분석하며 문제점을 찾아보겠습니다.
코드의 주된 문제점은 상어 이동과 자료구조 관리 부분에 집중돼 있습니다.
1. 상어 이동 로직(moveAllShark)의 연결 리스트 순회 오류
가장 치명적인 문제입니다. moveAllShark 함수에서 연결 리스트를 순회하며 노드를 분리(separateNode)하고 재배치하는데 이 과정에서 순회 로직이 깨지게 됩니다.
// moveAllShark 함수의 일부
target = sharkList[i];
while (target) {
next = target->next; // 1. 다음 노드를 미리 저장 (좋은 시도)
separateNode(target, i); // 2. 현재 노드를 리스트에서 분리
result = moveShark(target);
if (result) addNode(target, target->x);
target = target->next; // 3. 결정적인 오류 지점
} separateNode(target, i)가 호출되면 target 노드는 기존 리스트와의 연결이 모두 끊어집니다. 즉 target->prev와 target->next는 모두 nullptr가 됩니다.
그런데도 불구하고 target = target->next; 코드가 실행되면 이미 nullptr가 된 target->next를 다음 target으로 삼으려고 시도합니다. 결국 while 루프는 두 번째 상어부터는 처리하지 못하고 종료됩니다.
next 변수에 미리 다음 노드를 저장해두셨으니 루프의 마지막에서 target = next;로 수정해야 합니다.
2. 상어의 동시 이동 시뮬레이션 오류
문제의 조건은 모든 상어가 동시에 이동한 후 같은 칸에 모인 상어들 중 가장 큰 상어만 살아남는 것입니다. 하지만 현재 코드는 한 마리의 상어를 이동시키고 바로 visit 배열(새로운 격자판)에 위치시키며 충돌 검사를 합니다.
// moveShark 함수의 일부
if (!visit[target->y][target->x]) {
visit[target->y][target->x] = target; // 먼저 도착한 상어가 자리를 차지함
return true;
}
else {
// 나중에 도착한 상어와 크기 비교
if (visit[target->y][target->x]->size > target->size) {
// ...
}
// ...
} 이 방식은 상어를 어떤 순서로 이동시키는지에 따라 결과가 달라질 수 있습니다. 작은 상어가 먼저 이동해서 어떤 칸은 차지했는데 나중에 더 큰 상어가 같은 칸으로 이동하면 그제야 작은 상어가 잡아먹힙니다. 하지만 만약 큰 상어가 먼저 이동했다면 뒤늦게 온 작은 상어는 바로 잡아먹히겠죠. 동시이동이라는 규칙을 정확히 반영하지 못하게 됩니다.
해결책입니다.
- 모든 상어의 이동 후 위치를 임시 격자판에 기록합니다.
- 이 과정에서 만약 임시 격자판의 특정 칸에 이미 다른 상어가 있다면 크기를 비교해 더 큰 상어만 남깁니다.
- 모든 상어에 대한 계산이 끝나면 임시 격자판을 원래의 격자판으로 삼습니다.
3. 복잡한 상어 위치 계산 (moveShark)
벽에 부딪혔을 때 위치를 계산하는 현재 로직이 매우 복잡하고 오류가 발생할 가능성이 큽니다.
// moveShark 함수의 일부 (case 1: 위로 이동)
serial = 2 * Y - target->y + 1 + target->speed;
newIndex = serial % cycle;
// ... 이런 수식은 경계 값이나 특정 상황에서 잘못된 위치를 계산하기 쉽습니다.
속력 % ((칸 수 - 1) * 2) 공식을 활용하면 더 간결하고 정확하게 구현할 수 있습니다. 위아래로 움직이는 상어는 (R-1)*2를 주기로 왕복 운동을 합니다. 이 점을 이용해 실제 이동해야 할 유효 거리를 계산하고 현재 위치와 방향을 기준으로 최종 위치와 방향을 결정하는게 좋습니다.
마지막 조언입니다.
성능 때문에 그리하셨는지는 모르겠지만 연결 리스트 대신에 2차원 배열 SHARK* board[101][101]을 사용해 각 칸의 상어 정보를 직접 관리하는게 훨씬 직관적이고 간단합니다. R, C, M 초기 정보를 입력받은 다음에 M개의 상어 정보를 SHARK* board[r][c]에 저장하는 것이죠. 이상의 자세한 풀이 방법은 질문자님의 몫으로 남겨두겠습니다.
회원가입 혹은 광고 [X]를 누르면 내용이 보입니다
