A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)
공의 움직임을 구현할 때, 고려해야할 사항이 많은 문제이다.
이런 경우, 실수를 줄이기 위해 define을 해두면 편하다.
먼저 block의 상태는 아래와 같이 정의한다.
#define BLACKHOLE (-1)
#define EMPTY (0)
#define BLOCK_START (1)
#define BLOCK_END (5)
#define WORMHOLE_START (6)
#define WORMHOLE_END (10)BLOCK인 경우는 1 ~ 5, WORMHOLME은 6 ~ 10이므로 START, END로 경계를 나눈다.
방향에 관한 define은 아래와 같이 정한다.
그리고 LEFT ~ DOWN에 대응하는 dr, dc 배열을 정의한다.
REFLECT는 block의 평면, 그리고 CHANGE_LEFT ~ DOWN은 삼각 블록에 대응된다. (input에서 확인)
#define LEFT (0)
#define UP (1)
#define RIGHT (2)
#define DOWN (3)
#define REFLECT (0)
#define CHANGE_LEFT (1)
#define CHANGE_UP (2)
#define CHANGE_RIGHT (3)
#define CHANGE_DOWN (4)
/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };
BLOCK 구조체는 자신이 무슨 type인지 알아야 한다.
그리고 type이 BLOCK_START ~ BLOCK_END인 경우,
direction[LEFT ~ DOWN]에 REFLECT ~ CHANGE_DOWN을 mapping한다.
BALL은 현재 좌표와 방향이 필요하다.
WORMHOLE은 좌표만 필요하고 항상 쌍을 이룬다. 즉 wcnt 배열은 각 WORMHOLE 번호마다 2를 가지게 된다.
typedef struct st1
{
int direction[4];
int type;
}BLOCK;
BLOCK MAP[MAX][MAX];
typedef struct st2
{
int r;
int c;
int dir;
}BALL;
BALL ball;
typedef struct st3
{
int r;
int c;
}WORMHOLE;
WORMHOLE wormhole[10 + 2][2];
int wcnt[10 + 2];input 초기에는 wcnt를 모두 초기화한다. WORMHOLE이 6 ~ 10만 가능하므로, 6 ~ 10만 0으로 초기화한다.
그리고 MAP의 경계를 모두 5번 BLOCK으로 만든다.
5번 BLOCK은 모두 평면이므로 direction에 REFLECT를 선언해둔다.
void input()
{
scanf("%d", &N);
for (int w = 6; w <= 10; w++) wcnt[w] = 0;
for (int r = 0; r <= N + 1; r++)
{
for (int c = 0; c <= N + 1; c++)
{
MAP[r][c].type = 5;
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = REFLECT;
MAP[r][c].direction[RIGHT] = REFLECT;
MAP[r][c].direction[DOWN] = REFLECT;
}
}
...
}
MAP을 입력받을 때, 각 type별로 입력받는 방식이 달라진다.
BLOCK인 경우는 direction에 올바른 define을 선언하고, WORMHOLE인 경우는 좌표를 기억해둔다.
그 외에는 type만 입력받으면 된다.
void input()
{
/* init */
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
int type;
scanf("%d", &type);
MAP[r][c].type = type;
if (type == 1)
{
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = CHANGE_RIGHT;
MAP[r][c].direction[RIGHT] = CHANGE_UP;
MAP[r][c].direction[DOWN] = REFLECT;
}
else if (type == 2)
{
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = REFLECT;
MAP[r][c].direction[RIGHT] = CHANGE_DOWN;
MAP[r][c].direction[DOWN] = CHANGE_RIGHT;
}
else if (type == 3)
{
MAP[r][c].direction[LEFT] = CHANGE_DOWN;
MAP[r][c].direction[UP] = REFLECT;
MAP[r][c].direction[RIGHT] = REFLECT;
MAP[r][c].direction[DOWN] = CHANGE_LEFT;
}
else if (type == 4)
{
MAP[r][c].direction[LEFT] = CHANGE_UP;
MAP[r][c].direction[UP] = CHANGE_LEFT;
MAP[r][c].direction[RIGHT] = REFLECT;
MAP[r][c].direction[DOWN] = REFLECT;
}
else if (type == 5)
{
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = REFLECT;
MAP[r][c].direction[RIGHT] = REFLECT;
MAP[r][c].direction[DOWN] = REFLECT;
}
else if (WORMHOLE_START <= type && type <= WORMHOLE_END)
{
wormhole[type][wcnt[type]].r = r;
wormhole[type][wcnt[type]++].c = c;
}
}
}
}
아래의 그림은 1번 블럭이다.
그리고 1번 블럭은 define이 아래와 같이 Mapping된다.
if (type == 1)
{
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = CHANGE_RIGHT;
MAP[r][c].direction[RIGHT] = CHANGE_UP;
MAP[r][c].direction[DOWN] = REFLECT;
}
1번 BLOCK의 왼쪽과 아래쪽은 방향이 그대로 변경되기 때문에 REFLECT가 되고,
공이 아래로 움직이며 1번 BLOCK의 위(UP)를 만나면, 오른쪽으로 방향이 바뀌기 때문에 CHANGE_RIGHT,
공이 왼쪽으로 오면서, 1번 BLOCK의 오른쪽(RIGHT)를 만나면, 위로 방향이 바뀌기 때문에 CHANGE_UP이 된다.
나머지 2 ~ 5번 type도 같은 방법으로 define을 해주면 된다.
이렇게 선언하면 changeDir 배열을 이용해 공의 방향을 변경하기가 쉬워진다.
changeDir[방향][MAP.direction]은 아래와 같이 정의된다.
int changeDir[4][5];
int main(void)
{
changeDir[LEFT][REFLECT] = RIGHT;
changeDir[LEFT][CHANGE_LEFT] = -1;
changeDir[LEFT][CHANGE_UP] = UP;
changeDir[LEFT][CHANGE_RIGHT] = -1;
changeDir[LEFT][CHANGE_DOWN] = DOWN;
...
}
공이 LEFT에서 온 경우, REFLECT를 만나면 RIGHT로 변경한다.
공이 LEFT에서 올 경우에 CHANGE_LEFT와 CHANGE_RIGHT가 되는 경우는 있을 수 없다. (블럭을 잘 보자.)
따라서 debugging을 위해 -1을 담아둔다. 실제로 changeDir이 -1이 되는 경우가 없어야 한다.
공이 MAP의 CHANGE_UP을 만나면 UP, CHANGE_DOWN을 만나면 DOWN으로 변경된다.
마찬가지로 UP, RIGHT, DOWN은 최종 코드를 참고하자.
이제 공이 어떻게 방향을 바꾸는지 먼저 알아보자.
simulation을 진행할 때, checkDir이라는 배열을 선언하여 아래와 같이 정의한다.
int simulate(int sr, int sc, int dir)
{
int checkDir[4];
checkDir[LEFT] = RIGHT;
checkDir[RIGHT] = LEFT;
checkDir[UP] = DOWN;
checkDir[DOWN] = UP;
/* simulation */
}
지금까지 선언한 define으로 공의 방향을 어떻게 바꾸는지 1번 블럭의 예시로 보자.
공이 왼쪽에서 온다는 것은, BLOCK의 오른쪽 direction을 확인해야 한다. (checkDir[LEFT] = RIGHT)
1번 블럭의 경우 오른쪽은 CHANGE_UP이 선언되어 있다.
(MAP[r][c].direction[RIGHT] = CHANGE_UP;)
따라서 공의 방향이 왼쪽 → checkDir은 오른쪽이 된다. → checkDir[ball.dir] = 오른쪽
MAP[nr][nc].direction[오른쪽] → CHANGE_UP이 된다.
main문 초기에 changeDir을 선언하였으므로,
changeDir[공의 현재 방향][CHANGE_UP] → UP이 된다. (changeDir[LEFT][CHANGE_UP] = UP;)
최종적으로 공의 방향은 코드 한 줄로 변경할 수 있게 된다.
ball.dir = changeDir[ball.dir][MAP[nr][nc].direction[checkDir[ball.dir]]];문제에서 최대 점수가 되는 경우를 찾으라고 했으므로, 모든 빈칸에 대해 4방향으로 공을 놔두고 게임을 시작한다.
main문에서 매 tc마다 좌표가 비어있는 경우에 좌표 (r, c)에 공을 놔두고, dir 4방향을 넣어 simulate를 호출한다.
for (int tc = 1; tc <= T; tc++)
{
input();
int MAXANS = 0;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[r][c].type != 0) continue;
for (int dir = 0; dir < 4; dir++)
{
int score = simulate(r, c, dir);
if (MAXANS < score) MAXANS = score;
}
}
}
printf("#%d %d\n", tc, MAXANS);
}simulation은 아래와 같이 진행한다.
1) ball의 좌표와 방향을 넘겨받은 좌표와 방향으로 초기화한다.
2) 일단 다음 좌표로 이동한다.
3) 다음 좌표가 BLACKHOLE이거나 최초의 좌표라면 종료한다. (문제에서 제시한 종료 조건)
4) BLOCK_START와 BLOCK_END를 이용해 BLOCK으로 판별되면 score를 올리고, 공의 방향을 변경한다.
5) WORMHOLE인 경우는 wormhole배열에서 좌표를 찾아 공의 좌표를 바꾼다.
simulate는 공이 움직이는 동안 누적된 score를 return한다.
문제에서 반드시 종료되는 case만 주어진다고 하였으므로, 마지막 줄의 return -1은 도달할 수 없다.
int simulate(int sr, int sc, int dir)
{
int checkDir[4];
checkDir[LEFT] = RIGHT;
checkDir[RIGHT] = LEFT;
checkDir[UP] = DOWN;
checkDir[DOWN] = UP;
ball.r = sr, ball.c = sc;
ball.dir = dir;
int score = 0;
while (1)
{
output();
int nr, nc, mapType;
nr = ball.r + dr[ball.dir];
nc = ball.c + dc[ball.dir];
/* 일단 움직인다. */
ball.r = nr;
ball.c = nc;
mapType = MAP[nr][nc].type;
if (mapType == BLACKHOLE || (ball.r == sr && ball.c == sc)) return score;
// if (mapType == EMPTY); 빈 칸에서는 처리할 것이 없다.
if (BLOCK_START <= mapType && mapType <= BLOCK_END)
{
score++;
ball.dir = changeDir[ball.dir][MAP[nr][nc].direction[checkDir[ball.dir]]];
}
else if (WORMHOLE_START <= mapType && mapType <= WORMHOLE_END)
{
if (wormhole[mapType][0].r == nr && wormhole[mapType][0].c == nc)
{
ball.r = wormhole[mapType][1].r;
ball.c = wormhole[mapType][1].c;
}
else
{
ball.r = wormhole[mapType][0].r;
ball.c = wormhole[mapType][0].c;
}
}
}
printf("impossible case!\n");
return -1; /* impossible case */
}
부가 설명을 하면
2) 일단 다음 좌표로 이동한다.
ㄴ 시뮬레이션을 해보면 공이 블럭의 위치에 있어도 문제 될 것이 없다.
블럭의 좌표로 이동해도, define으로 공의 방향을 변경하였기 때문에 정상적으로 다음 위치로 이동할 수 있다.
5) WORMHOLE인 경우는 wormhole배열에서 좌표를 찾아 공의 좌표를 바꾼다.
ㄴ wormhole은 반드시 두 쌍이므로, wormhole[번호][0]과 [1]중 같은 것을 찾아, 다른 곳으로 좌표를 변경하였다.
최종 코드는 아래를 참고하자.
#include <stdio.h>
#define MAX (100 + 20)
#define BLACKHOLE (-1)
#define EMPTY (0)
#define BLOCK_START (1)
#define BLOCK_END (5)
#define WORMHOLE_START (6)
#define WORMHOLE_END (10)
#define LEFT (0)
#define UP (1)
#define RIGHT (2)
#define DOWN (3)
#define REFLECT (0)
#define CHANGE_LEFT (1)
#define CHANGE_UP (2)
#define CHANGE_RIGHT (3)
#define CHANGE_DOWN (4)
int T, N;
/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };
int changeDir[4][5];
typedef struct st1
{
int direction[4];
int type;
}BLOCK;
BLOCK MAP[MAX][MAX];
typedef struct st2
{
int r;
int c;
int dir;
}BALL;
BALL ball;
typedef struct st3
{
int r;
int c;
}WORMHOLE;
WORMHOLE wormhole[10 + 2][2];
int wcnt[10 + 2];
void input()
{
scanf("%d", &N);
for (int w = 6; w <= 10; w++) wcnt[w] = 0;
for (int r = 0; r <= N + 1; r++)
{
for (int c = 0; c <= N + 1; c++)
{
MAP[r][c].type = 5;
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = REFLECT;
MAP[r][c].direction[RIGHT] = REFLECT;
MAP[r][c].direction[DOWN] = REFLECT;
}
}
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
int type;
scanf("%d", &type);
MAP[r][c].type = type;
if (type == 1)
{
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = CHANGE_RIGHT;
MAP[r][c].direction[RIGHT] = CHANGE_UP;
MAP[r][c].direction[DOWN] = REFLECT;
}
else if (type == 2)
{
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = REFLECT;
MAP[r][c].direction[RIGHT] = CHANGE_DOWN;
MAP[r][c].direction[DOWN] = CHANGE_RIGHT;
}
else if (type == 3)
{
MAP[r][c].direction[LEFT] = CHANGE_DOWN;
MAP[r][c].direction[UP] = REFLECT;
MAP[r][c].direction[RIGHT] = REFLECT;
MAP[r][c].direction[DOWN] = CHANGE_LEFT;
}
else if (type == 4)
{
MAP[r][c].direction[LEFT] = CHANGE_UP;
MAP[r][c].direction[UP] = CHANGE_LEFT;
MAP[r][c].direction[RIGHT] = REFLECT;
MAP[r][c].direction[DOWN] = REFLECT;
}
else if (type == 5)
{
MAP[r][c].direction[LEFT] = REFLECT;
MAP[r][c].direction[UP] = REFLECT;
MAP[r][c].direction[RIGHT] = REFLECT;
MAP[r][c].direction[DOWN] = REFLECT;
}
else if (WORMHOLE_START <= type && type <= WORMHOLE_END)
{
wormhole[type][wcnt[type]].r = r;
wormhole[type][wcnt[type]++].c = c;
}
}
}
}
void output()
{
printf("ball r : %d, c %d, dir %d\n", ball.r, ball.c, ball.dir);
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (ball.r == r && ball.c == c) printf("[] ");
else printf("%2d ", MAP[r][c].type);
}
putchar('\n');
}
putchar('\n');
}
int simulate(int sr, int sc, int dir)
{
int checkDir[4];
checkDir[LEFT] = RIGHT;
checkDir[RIGHT] = LEFT;
checkDir[UP] = DOWN;
checkDir[DOWN] = UP;
ball.r = sr, ball.c = sc;
ball.dir = dir;
int score = 0;
while (1)
{
//output();
int nr, nc, mapType;
nr = ball.r + dr[ball.dir];
nc = ball.c + dc[ball.dir];
/* 일단 움직인다. */
ball.r = nr;
ball.c = nc;
mapType = MAP[nr][nc].type;
if (mapType == BLACKHOLE || (ball.r == sr && ball.c == sc)) return score;
// if (mapType == EMPTY); 빈 칸에서는 처리할 것이 없다.
if (BLOCK_START <= mapType && mapType <= BLOCK_END)
{
score++;
ball.dir = changeDir[ball.dir][MAP[nr][nc].direction[checkDir[ball.dir]]];
}
else if (WORMHOLE_START <= mapType && mapType <= WORMHOLE_END)
{
if (wormhole[mapType][0].r == nr && wormhole[mapType][0].c == nc)
{
ball.r = wormhole[mapType][1].r;
ball.c = wormhole[mapType][1].c;
}
else
{
ball.r = wormhole[mapType][0].r;
ball.c = wormhole[mapType][0].c;
}
}
}
printf("impossible case!\n");
return -1; /* impossible case */
}
int main(void)
{
changeDir[LEFT][REFLECT] = RIGHT;
changeDir[LEFT][CHANGE_LEFT] = -1;
changeDir[LEFT][CHANGE_UP] = UP;
changeDir[LEFT][CHANGE_RIGHT] = -1;
changeDir[LEFT][CHANGE_DOWN] = DOWN;
changeDir[UP][REFLECT] = DOWN;
changeDir[UP][CHANGE_LEFT] = LEFT;
changeDir[UP][CHANGE_UP] = -1;
changeDir[UP][CHANGE_RIGHT] = RIGHT;
changeDir[UP][CHANGE_DOWN] = -1;
changeDir[RIGHT][REFLECT] = LEFT;
changeDir[RIGHT][CHANGE_LEFT] = -1;
changeDir[RIGHT][CHANGE_UP] = UP;
changeDir[RIGHT][CHANGE_RIGHT] = -1;
changeDir[RIGHT][CHANGE_DOWN] = DOWN;
changeDir[DOWN][REFLECT] = UP;
changeDir[DOWN][CHANGE_LEFT] = LEFT;
changeDir[DOWN][CHANGE_UP] = -1;
changeDir[DOWN][CHANGE_RIGHT] = RIGHT;
changeDir[DOWN][CHANGE_DOWN] = -1;
scanf("%d", &T);
for (int tc = 1; tc <= T; tc++)
{
input();
int MAXANS = 0;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[r][c].type != 0) continue;
for (int dir = 0; dir < 4; dir++)
{
int score = simulate(r, c, dir);
if (MAXANS < score) MAXANS = score;
}
}
}
printf("#%d %d\n", tc, MAXANS);
}
return 0;
}
output 함수를 만들어두었으니 공이 제대로 움직이는지 잘 확인해보자.
위의 예시 (3, 4)에서 오른쪽 방향으로 출발하는 경우는 output이 아래와 같이 나타난다.
공의 위치는 []로 표시하였다.
3번 블럭을 만나 공의 방향이 아래로 잘 꺾인 것을 확인할 수 있다.
'알고리즘 > [ADV] 삼성 SW Expert Academy A형' 카테고리의 다른 글
| SWEA 5644 : 무선 충전 (모의 SW 역량테스트) (0) | 2021.04.30 |
|---|---|
| SWEA 5648 : 원자 소멸 시뮬레이션 (모의 SW 역량테스트) (0) | 2021.04.26 |
| SWEA 5653 : 줄기세포배양 (모의 SW 역량테스트) (0) | 2021.04.18 |
| SWEA 5656 : 벽돌 깨기 (모의 SW 역량테스트) (0) | 2021.04.15 |
| SWEA 5658 : 보물상자 비밀번호 (모의 SW 역량테스트) (0) | 2021.04.12 |
댓글