SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)
시뮬레이션 문제는 그대로 잘 구현하면 된다.
먼저 좌표를 저장할 RC 구조체를 선언한다.
people배열에는 사람의 좌표를, stair 배열에는 계단의 좌표를 저장한다.
list는 DFS로 사람을 나눌 때 사용한다.
2차원 배열 distance는 계단과 사람 사이의 거리이다.
distance[1][3]은 1번 계단과 3번 사람과의 사이를 의미한다.
stairLength는 계단을 내려가 이동이 완료되는 시간을 저장한다. (1/2번 계단에 대한 시간)
#define MAX (10 + 5)
int T, N;
int MAP[MAX][MAX];
int list[MAX];
typedef struct st
{
int r;
int c;
}RC;
RC people[MAX];
int pcnt; /* 사람은 0번 부터 시작 */
RC stair[2 + 3];
int stairLength[2 + 3];
int distance[2 + 3][MAX];
거리를 구하기 위한 abs, getLength 함수를 먼저 선언해두고, 입력을 받으면서 사람과 계단의 좌표를 저장한다.
그리고 매번 거리를 구할 필요없이 계단과 사람의 거리를 미리 distance에 저장한다.
int abs(int x)
{
return x > 0 ? x : -x;
}
int getLength(int r1, int c1, int r2, int c2)
{
return abs(r1 - r2) + abs(c1 - c2);
}
void input()
{
pcnt = 0;
scanf("%d", &N);
int scnt = 1; /* 1번 계단 부터 시작 */
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
int tmp;
scanf("%d", &tmp);
MAP[r][c] = tmp;
if (tmp == 1)
{
people[pcnt].r = r;
people[pcnt++].c = c;
}
else if (tmp >= 2)
{
stair[scnt].r = r;
stair[scnt].c = c;
stairLength[scnt++] = tmp;
}
}
}
for (int s = 1; s <= 2; s++)
for (int p = 0; p < pcnt; p++)
distance[s][p] = getLength(people[p].r, people[p].c, stair[s].r, stair[s].c);
}계단은 1, 2로 구분하였고 사람은 0번부터 시작한다.
먼저 사람을 A 그룹과 B 그룹으로 나눠야한다.
A 그룹과 B 그룹은 DFS를 이용해서 나눈다. (list 배열이 0이면 A 그룹, 1이면 B 그룹이다.)
나누어진 list를 보고 simulate를 실행하고 MINANS를 갱신하면 된다.
void DFS(int L)
{
if (L == pcnt)
{
int tmp = simulate();
if (tmp < MINANS) MINANS = tmp;
return;
}
list[L] = 0;
DFS(L + 1);
list[L] = 1;
DFS(L + 1);
}
위에서 설명한대로 list를 보고 peopleA와 peopleB에 index를 넣어서 사람을 나눈다.
calculate는 people 배열과 크기 그리고 계단의 번호를 넘기면 소모되는 시간을 return한다.
사람 A가 계단 1에 간 경우 vs 사람 B가 계단 2에 간 경우를 비교해서 더 큰 소모 시간을 return한다.
int simulate()
{
int peopleA[MAX] = { 0 };
int peopleB[MAX] = { 0 };
int acnt, bcnt, timeA, timeB;
acnt = bcnt = 0;
for (int i = 0; i < pcnt; i++)
{
if (list[i] == 0) peopleA[acnt++] = i;
else peopleB[bcnt++] = i;
}
timeA = calculate(peopleA, acnt, 1);
timeB = calculate(peopleB, bcnt, 2);
return (timeA > timeB) ? timeA : timeB;
}사람 A가 계단 2에 간 경우 vs 사람 B가 계단 1에 간 경우도 DFS에 의해 만들어진다.
people의 번호를 보고 input에서 만든 distance를 이용해 distanceArr를 만든다.
짧은 거리의 사람이 먼저 도착하게 하기 위해 sorting한다.
A형에서는 정렬 알고리즘을 요구하지 않기 때문에 간단히 O(N2) 정렬을 해도 된다.
int calculate(int people[MAX], int count, int stairNumber)
{
int time;
int distanceArr[11] = { 0 };
/* 거리 저장 */
for (int i = 0; i < count; i++)
distanceArr[i] = distance[stairNumber][people[i]];
/* sorting */
for (int i = 0; i < count - 1; i++)
{
for (int k = i + 1; k < count; k++)
{
if (distanceArr[i] > distanceArr[k])
{
int tmp = distanceArr[i];
distanceArr[i] = distanceArr[k];
distanceArr[k] = tmp;
}
}
}
...
return time;
}
참고로 사람의 번호는 중요하지 않다.
번호와 상관없이 people 가야 할 계단이 결정되면, 거리가 결정된다.
따라서 번호와 상관없이 소모된 시간이 결정된다.
people은 계단으로 이동하고, 계단에서 시간을 소모한다. 이 때 최대 3명까지만 계단을 내려간다.
따라서 queue를 이용해 계단으로 내리는 것을 구현한다.
단, read point를 기준으로 최대 3명만 계단을 내려갈 수 있다.
여기서 queue는 downStair 배열로 정의한다. (계단에 있는 사람이 계단을 내려가는데 남은 시간)
이제 people을 계단으로 이동시켜보자.
downStair에 값이 들어가는 것은 people이 계단에 도착했을 때이다.
모든 distanceArr에 대해 거리 1을 감소하고, 거리가 0이 된 경우에 downStair에 넣는다.
downStair는 input에서 저장한 stairLength[계단의 번호] (계단에 내려가는데 걸리는 시간)로 넣어야 한다.
while (1)
{
time++;
/* 계단으로 이동 */
for (int i = 0; i < count; i++) distanceArr[i] -= 1;
for (int i = 0; i < count; i++)
{
if (distanceArr[i] == 0)
downStair[wp++] = stairLength[stairNumber];
}
...
}
downStair 배열은 사람이 들어왔을 때, 계단을 내려가는데 걸리는 시간을 저장하고 있다.
최대 3명만 계단에 내려가기 위해 rp ~ rp + 3까지만 downStair의 시간을 1씩 감소한다.
그러나 downStair에 사람이 3명 미만인 경우가 있으므로, wp와 비교해서 wp보다 큰 경우는 break로 빠져나간다.
while (1)
{
time++;
/* 계단으로 이동 */
...
/* 최대 3명만 계단을 내려간다. */
for (int i = rp; i < rp + 3; i++)
{
if (i > wp) break; /* 3명이 아니면 wp보다 큰 경우 종료하면 된다. */
downStair[i] -= 1;
}
...
}
계단을 내려가는데 걸리는 시간을 소모하여서 0이 되었으면 read pointer를 올려서 pop한다.
pop을 하면 rp가 올라가게 되고, rp가 people의 수와 같을 때 while문을 종료하면 된다.
while (1)
{
time++;
/* 계단으로 이동 */
...
/* 최대 3명만 계단을 내려간다. */
...
for (int i = rp; i < wp; i++)
if (downStair[i] == 0) rp++;
if (rp == count) break;
}
마지막으로 return하는 time은 1을 더해서 return한다.
문제의 시뮬레이션에서 N번 사람이 이동 완료한 후의 시간을 원하기 때문이다.
최종 코드는 아래와 같다.
#include <stdio.h>
#define MAX (10 + 5)
int T, N;
int MAP[MAX][MAX];
int list[MAX];
typedef struct st
{
int r;
int c;
}RC;
RC people[MAX];
int pcnt; /* 사람은 0번 부터 시작 */
RC stair[2 + 3];
int stairLength[2 + 3];
int distance[2 + 3][MAX];
int abs(int x)
{
return x > 0 ? x : -x;
}
int getLength(int r1, int c1, int r2, int c2)
{
return abs(r1 - r2) + abs(c1 - c2);
}
void input()
{
pcnt = 0;
scanf("%d", &N);
int scnt = 1; /* 1번 계단 부터 시작 */
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
int tmp;
scanf("%d", &tmp);
MAP[r][c] = tmp;
if (tmp == 1)
{
people[pcnt].r = r;
people[pcnt++].c = c;
}
else if (tmp >= 2)
{
stair[scnt].r = r;
stair[scnt].c = c;
stairLength[scnt++] = tmp;
}
}
}
for (int s = 1; s <= 2; s++)
for (int p = 0; p < pcnt; p++)
distance[s][p] = getLength(people[p].r, people[p].c, stair[s].r, stair[s].c);
}
int calculate(int people[MAX], int count, int stairNumber)
{
int time;
int distanceArr[11] = { 0 };
/* 거리 저장 */
for (int i = 0; i < count; i++)
distanceArr[i] = distance[stairNumber][people[i]];
/* sorting */
for (int i = 0; i < count - 1; i++)
{
for (int k = i + 1; k < count; k++)
{
if (distanceArr[i] > distanceArr[k])
{
int tmp = distanceArr[i];
distanceArr[i] = distanceArr[k];
distanceArr[k] = tmp;
}
}
}
int downStair[MAX]; /* queue */
int wp, rp;
time = 1;
wp = rp = 0;
while (1)
{
time++;
/* 계단으로 이동 */
for (int i = 0; i < count; i++) distanceArr[i] -= 1;
for (int i = 0; i < count; i++)
{
if (distanceArr[i] == 0)
downStair[wp++] = stairLength[stairNumber];
}
/* 최대 3명만 계단을 내려간다. */
for (int i = rp; i < rp + 3; i++)
{
if (i > wp) break; /* 3명이 아니면 wp보다 큰 경우 종료하면 된다. */
downStair[i] -= 1;
}
for (int i = rp; i < wp; i++)
if (downStair[i] == 0) rp++;
if (rp == count) break;
}
return time + 1;
}
int simulate()
{
int peopleA[MAX] = { 0 };
int peopleB[MAX] = { 0 };
int acnt, bcnt, timeA, timeB;
acnt = bcnt = 0;
for (int i = 0; i < pcnt; i++)
{
if (list[i] == 0) peopleA[acnt++] = i;
else peopleB[bcnt++] = i;
}
timeA = calculate(peopleA, acnt, 1);
timeB = calculate(peopleB, bcnt, 2);
return (timeA > timeB) ? timeA : timeB;
}
int MINANS = 0x7fff0000;
void DFS(int L)
{
if (L == pcnt)
{
int tmp = simulate();
if (tmp < MINANS) MINANS = tmp;
return;
}
list[L] = 0;
DFS(L + 1);
list[L] = 1;
DFS(L + 1);
}
int main(void)
{
scanf("%d", &T);
for (int tc = 1; tc <= T; tc++)
{
input();
MINANS = 0x7fff0000;
DFS(0);
printf("#%d %d\n", tc, MINANS);
}
return 0;
}'알고리즘 > [ADV] 삼성 SW Expert Academy A형' 카테고리의 다른 글
| SWEA 2117 : 홈 방범 서비스 (모의 SW 역량테스트) (0) | 2021.05.11 |
|---|---|
| SWEA 2382 : 미생물 격리 (모의 SW 역량테스트) (1) | 2021.05.09 |
| SWEA 4013 : 특이한 자석 (모의 SW 역량테스트) (0) | 2021.05.05 |
| SWEA 4014 : 활주로 건설 (모의 SW 역량테스트) (0) | 2021.05.02 |
| SWEA 5644 : 무선 충전 (모의 SW 역량테스트) (0) | 2021.04.30 |
댓글