www.acmicpc.net/workbook/view/1152 (A형 문제집)
시뮬레이션 문제는 그대로 구현하면 된다.
아래의 내용을 구현해보자.
1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.
int main(void)
{
int ans;
input();
ans = 0;
for (int c = 1; c <= C; c++) /* 1. 낚시왕이 오른쪽으로 한 칸 이동한다. */
{
ans += catchShark(c); /* 2. 상어를 잡는다. */
moveShark(); /* 3. 상어가 이동한다. */
}
printf("%d\n", ans);
return 0;
}
1. 낚시왕의 이동은 main에서 for문을 이용하여 이동한다.
2. catchShark, 낚시왕이 상어를 잡을 때, 상어의 크기를 return한다.
3. moveShark, 상어를 움직인다.
catchShark는 낚시왕이 가장 윗부분의 상어만 잡으면 되므로 아래와 같이 구현하면 된다.
int catchShark(int c)
{
for (int r = 1; r <= R; r++)
{
if (shark[r][c].size)
{
int ret = shark[r][c].size;
/* 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
상어를 잡으면 격자판에서 잡은 상어가 사라진다. */
shark[r][c].size = 0;
return ret;
}
}
return 0; /* 상어가 없는 경우는 0을 return */
}
상어를 잡았을 경우, shark의 size를 0으로 만들어서 상어를 지우자.
그리고 상어가 없는 경우를 고려해 마지막엔 0을 return하자.
moveShark를 구현할 때는, 상어를 직접 움직이면 된다.
문제에서 주어진 상어가 움직이는 방향을 참고하여 dr, dc 배열을 만들자.
0의 입력이 없으므로 0번 배열은 버린다.
/* 순서대로 1: 위, 2: 아래, 3: 오른쪽, 4: 왼쪽 */
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, 1, -1 };
그리고 아래의 조건, 이동이 완료된 상어가 (r, c)에 중복으로 있는 경우, 상어를 잡아먹는 경우가 발생한다.
따라서 상어가 존재하는지는 shark[r][c]를 참고하고, 실제 이동은 tmpShark[r'][c']에 한다.
이동 + 상어가 상어를 잡아먹으면, tmpShark를 shark[r][c]에 다시 복사한다.
그리고 경계를 넘는 경우에 방향이 1 → 2, 2 → 1, 3 → 4, 4 → 3 으로 변하므로, 배열을 이용해 방향을 변경한다.
void moveShark()
{
int changeDir[5] = { 0, 2, 1, 4, 3 }; /* 방향 변경 배열 */
SHARK tmpShark[MAX][MAX] = {}; /* tmpShark 초기화 */
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
/* 상어의 이동 + 먹기 */
/* 계산이 완료되었으므로 다시 shark 갱신 */
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
shark[r][c] = tmpShark[r][c];
}
이제 상어를 움직여보자.
shark[r][c]의 size가 0이면 상어가 없다고 정의하자.
그렇지 않다면, 상어의 방향이 위나 아래인 경우 (dir <= 2) 와 오른쪽과 왼쪽인 경우로 나눌 수 있다.
for (int r = 1; r <= R; r++)
{
for (int c = 1; c <= C; c++)
{
if (shark[r][c].size == 0) continue;
SHARK shk = shark[r][c];
if (shk.dir <= 2) { ... } /* 위나 아래 */
else { ... } /* 오른쪽이나 왼쪽 */
}
}
상어는 상어의 speed 만큼 움직이므로, 위나 아래인 경우는 dr을 이용해서 움직인다.
if (shk.dir <= 2) /* 위나 아래의 경우 */
{
int move = shk.speed;
int sr, dir;
sr = r; /* 시작 row */
dir = shk.dir; /* 방향 저장 */
for (int m = 0; m < move; m++)
{
int nr;
nr = sr + dr[dir];
if (nr < 1) /* 위로 경계를 벗어나면 2로 위치 변경, 방향 변경 */
{
dir = changeDir[dir];
sr = 2;
continue;
}
if (nr > R) /* 아래로 경계를 벗어나면 R - 1로 위치 변경, 방향 변경 */
{
dir = changeDir[dir];
sr = R - 1;
continue;
}
sr = nr; /* 경계를 벗어나지 않으면 sr 갱신 */
}
/* 이미 상어가 있다면, 갱신, 그리고 방향은 현재 방향으로 갱신 */
if (tmpShark[sr][c].size < shark[r][c].size)
{
tmpShark[sr][c] = shark[r][c];
tmpShark[sr][c].dir = dir;
}
}
이미 상어가 있는 경우 if문으로 size를 체크해서 갱신하고, 방향은 원래 shark[r][c].dir이 아닌,
현재 계산에 의해 변경된 방향을 넣어야 한다.
또한, 위의 로직대로라면 상어가 없는 경우에도, tmpShark[sr][c].size가 0이기 때문에, 새로운 상어가 들어오게 된다.
오른쪽/왼쪽 이동은 전체 코드를 참고하자.
#include <stdio.h>
#define MAX (100 + 20)
int R, C, M;
typedef struct st
{
int speed;
int dir;
int size;
}SHARK;
SHARK shark[MAX][MAX];
void input()
{
scanf("%d %d %d", &R, &C, &M);
for (int i = 0; i < M; i++)
{
int r, c, s, d, z;
scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
shark[r][c].speed = s;
shark[r][c].dir = d;
shark[r][c].size = z;
}
}
void output()
{
for (int r = 1; r <= R; r++)
{
for (int c = 1; c <= C; c++)
printf("%d ", shark[r][c].size);
putchar('\n');
}
putchar('\n');
}
int catchShark(int c)
{
for (int r = 1; r <= R; r++)
{
if (shark[r][c].size)
{
int ret = shark[r][c].size;
/* 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
상어를 잡으면 격자판에서 잡은 상어가 사라진다. */
shark[r][c].size = 0;
return ret;
}
}
return 0; /* 상어가 없는 경우는 0을 return */
}
/* 순서대로 1: 위, 2: 아래, 3: 오른쪽, 4: 왼쪽 */
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, 1, -1 };
void moveShark()
{
int changeDir[5] = { 0, 2, 1, 4, 3 };
SHARK tmpShark[MAX][MAX] = {};
for (int r = 1; r <= R; r++)
{
for (int c = 1; c <= C; c++)
{
if (shark[r][c].size == 0) continue;
SHARK shk = shark[r][c];
if (shk.dir <= 2) /* 위나 아래의 경우 */
{
int move = shk.speed;
int sr, dir;
sr = r;
dir = shk.dir;
for (int m = 0; m < move; m++)
{
int nr;
nr = sr + dr[dir];
if (nr < 1)
{
dir = changeDir[dir];
sr = 2;
continue;
}
if (nr > R)
{
dir = changeDir[dir];
sr = R - 1;
continue;
}
sr = nr;
}
if (tmpShark[sr][c].size < shark[r][c].size)
{
tmpShark[sr][c] = shark[r][c];
tmpShark[sr][c].dir = dir;
}
}
else /* 오른쪽이나 왼쪽의 경우 */
{
int move = shk.speed;
int sc, dir;
sc = c;
dir = shk.dir;
for (int m = 0; m < move; m++)
{
int nc;
nc = sc + dc[dir];
if (nc < 1)
{
dir = changeDir[dir];
sc = 2;
continue;
}
if (nc > C)
{
dir = changeDir[dir];
sc = C - 1;
continue;
}
sc = nc;
}
if (tmpShark[r][sc].size < shark[r][c].size)
{
tmpShark[r][sc] = shark[r][c];
tmpShark[r][sc].dir = dir;
}
}
}
}
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
shark[r][c] = tmpShark[r][c];
}
int main(void)
{
int ans;
input();
ans = 0;
for (int c = 1; c <= C; c++) /* 1. 낚시왕이 오른쪽으로 한 칸 이동한다. */
{
ans += catchShark(c); /* 2. 상어를 잡는다. */
moveShark(); /* 3. 상어가 이동한다. */
//output();
}
printf("%d\n", ans);
return 0;
}마지막으로 최적화를 해보자.
상어가 만약 1000000번 움직인다면? moveShark에서 1000000번 for문을 돌게 된다.
상어가 언제 원래의 좌표로 돌아오는지 알면 최적화가 가능하다.
위의 상어를 실제로 움직여보자.
0s : r = 2 (방향은 위)
1s : r = 1
2s : r = 2 (방향 전환, 아래)
3s : r = 3
4s : r = 4
5s : r = 3 (방향 전환, 위)
6s : r = 2 (방향은 위)
6초가 지났더니, 상어가 원상복귀하게 되었다.
다른 경우도 계산을 해보면 move는 상어 speed의 ( (R - 1) * 2 ) 의 나머지 만큼 움직이게 된다는 것을 알 수 있다.
마찬가지로 오른쪽/왼쪽의 경우는 ( (C - 1) * 2 )의 나머지 만큼 움직인다.
for (int r = 1; r <= R; r++)
{
for (int c = 1; c <= C; c++)
{
if (shark[r][c].size == 0) continue;
SHARK shk = shark[r][c];
if (shk.dir <= 2) /* 위나 아래의 경우 */
{
int move = shk.speed % ((R - 1) * 2);
...
}
else
{
int move = shk.speed % ((C - 1) * 2);
...
}
...
}
...
}
moveShark의 move를 위와 같이 변경하면 성능이 훨씬 개선된다.
'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글
| BOJ 17142 : 연구소 3 (삼성 SW TEST A형) (0) | 2021.03.17 |
|---|---|
| BOJ 17140 : 이차원 배열과 연산 (삼성 SW TEST A형) (0) | 2021.03.14 |
| BOJ 17144 : 미세먼지 안녕! (삼성 SW TEST A형) (0) | 2021.03.08 |
| BOJ 16236 : 아기 상어 (삼성 SW TEST A형) (0) | 2021.03.06 |
| BOJ 16235 : 나무 재테크 (삼성 SW TEST A형) (0) | 2021.03.04 |
댓글