A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)
www.acmicpc.net/workbook/view/1152 (A형 문제집)
달팽이 배열을 만들고, 그 배열에 해당하는 index를 관리하면 해결할 수 있다.
아래는 변수에 대한 설명이다.
MAP : 입력에 주어지는 2차원 배열
snail : 달팽이 배열의 index 관리를 위한 2차원 배열
indexArray : indexArray[i] = i로, 달팽이 배열의 index를 만들기 위한 배열
indexValue : 달팽이 배열을 1차원 배열로 볼 때의 값을 저장한 배열
icnt : indexValue 배열의 size
bombCount : 폭발한 1 ~ 3번 구슬의 개수
MAP은 좌표의 (1, 1)부터 받는다.
#define MAX (50 + 5)
int N, M;
int MAP[MAX][MAX];
int snail[MAX][MAX];
int indexArray[MAX * MAX];
int indexValue[MAX * MAX];
int icnt;
int bombCount[4];
void input()
{
scanf("%d %d", &N, &M);
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scanf("%d", &MAP[r][c]);
for (int i = 0; i < N * N; i++) indexArray[i] = i;
}먼저 달팽이 배열을 만들고, 달팽이 배열의 index를 1차원 배열로 만들자.
(달팽이 배열은 BOJ 1913 : 달팽이를 참고하자. BOJ 1913에서 방향만 잘 변경해주면 된다.)
makeSnail 함수는 달팽이 배열을 만들 2차원 배열과 순서대로 입력될 1차원 배열을 넘겨받는다.
1차원 배열의 값은 map에 순차적으로 저장되고, indexValue는 MAP의 값을 순서대로 저장한다.
즉, 달팽이 배열을 순서대로 순회하면서 map ← arr의 값을 저장하고 indexValue ← MAP의 값을 저장한다.
/* ←, ↓, →, ↑ */
int dr[] = { 0, 1, 0, -1 };
int dc[] = { -1, 0, 1, 0 };
void makeSnail(int map[MAX][MAX], int arr[])
{
int sr, sc, dir, index, size;
dir = index = size = 0;
sr = sc = N / 2 + 1;
map[sr][sc] = arr[index++];
for (int i = 0; i < 2 * N - 1; i++)
{
if (i % 2 == 0) size++;
for (int s = 0; s < size; s++)
{
int nr, nc;
nr = sr + dr[dir];
nc = sc + dc[dir];
/* 순서 주의 */
map[nr][nc] = arr[index];
indexValue[index++] = MAP[nr][nc];
sr = nr;
sc = nc;
}
dir++;
if (dir == 4) dir = 0;
}
}
makeSnail(snail, indexArray)을 실행하면 아래와 같이 snail이 완성된다.
main에서 input을 입력 받은 후, makeSnail을 실행한다.
snail 배열을 다시 순서대로 돌면서 indexValue에 값을 입력한다.
/* 0, ↑, ↓, ←, → */
int drr[] = { 0, -1, 1, 0, 0 };
int dcc[] = { 0, 0, 0, -1, 1 };
int main()
{
input();
makeSnail(snail, indexArray);
/* simulation */
return 0;
}
최종적으로 아래의 2차원 배열이 만들어진다.
MAP에서 N번째 값을 알고 싶다면? indexValue[N]을 참고하면 된다.
예시로 달팽이 배열의 4번째와 21번째에 indexValue[4] = 2, indexValue[21] = 2가 저장된 것을 알 수 있다.
시뮬레이션의 첫 번째 단계는 블리자드 마법 = 배열을 지우는 것이다.
drr, dcc 배열을 문제에서 주어진 방향에 맞게 선언한 후, d 방향에서 s 만큼 배열을 지운다.
snail 배열에 index가 저장되어있으므로 indexValue에도 값을 지운다.
/* 0, ↑, ↓, ←, → */
int drr[] = { 0, -1, 1, 0, 0 };
int dcc[] = { 0, 0, 0, -1, 1 };
int main()
{
input();
makeSnail(snail, indexArray);
/* simulation */
for (int i = 0; i < M; i++)
{
int d, s, sr, sc;
scanf("%d %d", &d, &s);
sr = sc = N / 2 + 1;
/* 배열 지우기 */
for (int k = 1; k <= s; k++)
{
int nr, nc, index;
nr = sr + drr[d] * k;
nc = sc + dcc[d] * k;
MAP[nr][nc] = 0;
index = snail[nr][nc];
indexValue[index] = 0;
}
...
}
printf("%d\n", 1 * bombCount[1] + 2 * bombCount[2] + 3 * bombCount[3]);
return 0;
}이제 MAP을 볼 필요 없이 1차원 배열인 indexValue만을 이용해 문제를 풀 수 있다.
빈칸이 생겨 구슬이 이동하고, 구슬이 폭발하는 과정은 1차원 배열에서 해도 같은 결과가 나온다.
(달팽이 배열 그대로 구현하면 매우 힘들고, 디버깅도 어렵다.)
최종적으로 1차원 배열을 다시 MAP에 옮기기만 하면 된다.
먼저 빈칸을 채우는 함수는 아래와 같이 구현한다.
1) 배열의 크기 icnt를 tcnt로 복사하고, icnt를 1로 만든다.
2) arr[i]가 0이 아닌 경우에만 arr[icnt]에 복사한다.
3) 남은 칸, icnt 부터 N * N을 0으로 만든다.
위 과정을 진행하면 빈칸을 모두 없앨 수 있다.
void deleteEmpty(int arr[])
{
int tcnt = icnt;
icnt = 1;
for (int i = 1; i < tcnt; i++)
if (arr[i] != 0) arr[icnt++] = arr[i];
/* 남은 칸을 0으로 만든다. */
for (int i = icnt; i < N * N; i++) arr[i] = 0;
}폭발하는 함수는 조금 까다롭다.
폭발이 발생하고 빈칸을 채우는 과정은 폭발이 발생하지 않을 때까지 반복해야 한다.
따라서 폭발이 발생하는 경우는 flag를 1로, 폭발이 발생하지 않으면 flag = 0을 return하도록 한다.
최소 하나의 구슬이 있으므로, count는 1로 초기화한다.
그리고 배열의 첫 번째부터 시작하면서 같은 값인 경우 count를 증가시킨다.
구슬이 달라질 때,
count가 4 미만인 경우는 start ~ start + count 까지의 값을 arr에 다시 복사한다.
count가 4 이상인 경우는 flag = 1로 만들어 폭발했다는 것을 표시한다.
이 경우에는 arr에 복사하지 않는다.
그리고 bombCount에 폭발한 구슬을 누적한다.
마지막으로 count를 1로 초기화하고 start를 다음 칸으로 바꿔준다.
int explode(int arr[])
{
int flag, count, start, tcnt;
flag = 0;
start = count = 1;
tcnt = icnt;
icnt = 1;
for (int i = 1; i < tcnt; i++)
{
if (arr[i] == arr[i + 1]) count++;
else
{
if (count < 4)
for (int k = start; k < start + count; k++) arr[icnt++] = arr[k];
else
{
flag = 1;
bombCount[arr[i]] += count;
}
count = 1;
start = i + 1;
}
}
/* 남은 칸을 0으로 만든다. */
for (int i = icnt; i < N * N; i++) arr[i] = 0;
return flag;
}남은 칸을 0으로 채워야 하는 것도 잊지 말자.
최종적으로 deleteEmpty를 실행한 뒤, explode와 deleteEmpty를 while문을 이용해 반복한다.
폭발이 없는 경우에만 while문을 빠져나올 수 있다.
int main()
{
input();
makeSnail(snail, indexArray);
/* simulation */
for (int i = 0; i < M; i++)
{
...
/* 배열 지우기 */
icnt = N * N;
deleteEmpty(indexValue);
while (1)
{
int ret = explode(indexValue);
if (ret == 0) break;
deleteEmpty(indexValue);
}
...
}
...
return 0;
}마지막으로 폭발이 완료된 indexValue를 문제에서 주어진 대로 변경한다.
배열의 같은 값을 세면서, 달라지는 타이밍에 newArr에 count와 구슬 번호(배열의 값)를 입력하면 된다.
N * N보다 큰 경우는 구슬이 사라진다고 하였으므로 break로 빠져나간다.
newArr를 arr에 다시 복사하고, 남은 칸은 0으로 만든다.
이전에 만든 makeSnail에 MAP과 arr를 넣어주면 arr가 달팽이 모양으로 MAP을 변경한다.
void makeNewMAP(int arr[])
{
int newArr[MAX * MAX] = { 0 };
int ncnt, count;
ncnt = count = 1;
for (int i = 1; i < icnt; i++)
{
if (arr[i] == arr[i + 1]) count++;
else
{
newArr[ncnt++] = count;
newArr[ncnt++] = arr[i];
count = 1;
}
if (ncnt == N * N) break;
}
for (int i = 1; i < ncnt; i++) arr[i] = newArr[i];
for (int i = ncnt; i < N * N; i++) arr[i] = 0;
makeSnail(MAP, arr);
}
최종 코드는 아래와 같다.
#include <stdio.h>
#define MAX (50 + 5)
int N, M;
int MAP[MAX][MAX];
int snail[MAX][MAX];
int indexArray[MAX * MAX];
int indexValue[MAX * MAX];
int icnt;
int bombCount[4];
void input()
{
scanf("%d %d", &N, &M);
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scanf("%d", &MAP[r][c]);
for (int i = 0; i < N * N; i++) indexArray[i] = i;
}
void output(int map[MAX][MAX])
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
printf("%2d ", map[r][c]);
putchar('\n');
}
putchar('\n');
}
/* ←, ↓, →, ↑ */
int dr[] = { 0, 1, 0, -1 };
int dc[] = { -1, 0, 1, 0 };
void makeSnail(int map[MAX][MAX], int arr[])
{
int sr, sc, dir, index, size;
dir = index = size = 0;
sr = sc = N / 2 + 1;
map[sr][sc] = arr[index++];
for (int i = 0; i < 2 * N - 1; i++)
{
if (i % 2 == 0) size++;
for (int s = 0; s < size; s++)
{
int nr, nc;
nr = sr + dr[dir];
nc = sc + dc[dir];
/* 순서 주의 */
map[nr][nc] = arr[index];
indexValue[index++] = MAP[nr][nc];
sr = nr;
sc = nc;
}
dir++;
if (dir == 4) dir = 0;
}
}
void deleteEmpty(int arr[])
{
int tcnt = icnt;
icnt = 1;
for (int i = 1; i < tcnt; i++)
if (arr[i] != 0) arr[icnt++] = arr[i];
/* 남은 칸을 0으로 만든다. */
for (int i = icnt; i < N * N; i++) arr[i] = 0;
}
int explode(int arr[])
{
int flag, count, start, tcnt;
flag = 0;
start = count = 1;
tcnt = icnt;
icnt = 1;
for (int i = 1; i < tcnt; i++)
{
if (arr[i] == arr[i + 1]) count++;
else
{
if (count < 4)
for (int k = start; k < start + count; k++) arr[icnt++] = arr[k];
else
{
flag = 1;
bombCount[arr[i]] += count;
}
count = 1;
start = i + 1;
}
}
/* 남은 칸을 0으로 만든다. */
for (int i = icnt; i < N * N; i++) arr[i] = 0;
return flag;
}
void makeNewMAP(int arr[])
{
int newArr[MAX * MAX] = { 0 };
int ncnt, count;
ncnt = count = 1;
for (int i = 1; i < icnt; i++)
{
if (arr[i] == arr[i + 1]) count++;
else
{
newArr[ncnt++] = count;
newArr[ncnt++] = arr[i];
count = 1;
}
if (ncnt == N * N) break;
}
for (int i = 1; i < ncnt; i++) arr[i] = newArr[i];
for (int i = ncnt; i < N * N; i++) arr[i] = 0;
makeSnail(MAP, arr);
}
/* 0, ↑, ↓, ←, → */
int drr[] = { 0, -1, 1, 0, 0 };
int dcc[] = { 0, 0, 0, -1, 1 };
int main()
{
input();
makeSnail(snail, indexArray);
/* simulation */
for (int i = 0; i < M; i++)
{
int d, s, sr, sc;
scanf("%d %d", &d, &s);
sr = sc = N / 2 + 1;
/* 배열 지우기 */
for (int k = 1; k <= s; k++)
{
int nr, nc, index;
nr = sr + drr[d] * k;
nc = sc + dcc[d] * k;
MAP[nr][nc] = 0;
index = snail[nr][nc];
indexValue[index] = 0;
}
icnt = N * N;
deleteEmpty(indexValue);
while (1)
{
int ret = explode(indexValue);
if (ret == 0) break;
deleteEmpty(indexValue);
}
makeNewMAP(indexValue);
}
printf("%d\n", 1 * bombCount[1] + 2 * bombCount[2] + 3 * bombCount[3]);
return 0;
}'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글
| BOJ 23289 : 온풍기 안녕! (삼성 SW TEST A형) (0) | 2021.11.06 |
|---|---|
| BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST A형) (0) | 2021.10.25 |
| BOJ 21610 : 마법사 상어와 비바라기 (삼성 SW TEST A형) (0) | 2021.04.30 |
| BOJ 21609 : 상어 중학교 (삼성 SW TEST A형) (0) | 2021.04.29 |
| BOJ 21608 : 상어 초등학교 (삼성 SW TEST A형) (0) | 2021.04.26 |
댓글