알고리즘/[ADV] 삼성 SW 역량 테스트 A형
[코드트리] 개구리의 여행 (삼성 SW 역량테스트 2025 상반기 오전 2번, B형)
피로물든딸기
2025. 5. 1. 19:24
반응형
SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)
2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,
A형 1문제 + B형 문제 1문제가 출제됩니다.
참고
- B형 필수 : 우선순위 큐 Priority Queue
https://www.codetree.ai/ko/frequent-problems/problems/frog-journey/description
현재 개구리의 점프력에서 갈 수 있는 (r, c)의 최소 거리를 dist[jump][r][c]에 저장한다.
isMove는 (r, c)에서 (nr, nc)로 이동할 수 있는지 여부를 미리 전처리하는데 사용한다.
#define MAX (50 + 5)
#define INF (0x7fff0000)
int T;
int N, Q;
char MAP[MAX][MAX];
int dist[5 + 1][MAX][MAX];
bool isMove[MAX][MAX][MAX][MAX];
makeIsMove에서 모든 좌표에 대해 안전한 돌(.)인 경우,
4방향 5칸을 이동하면서 좌표를 벗어나거나 천적이 사는 돌(#)을 만나는 경우는 break로 빠져나가고
미끄러운 돌(S)인 경우는 continue로 넘어가면서 isMove[r][c][nr][nc] = true로 마킹한다.
void makeIsMove()
{
for (int a = 1; a <= N; a++)
for (int b = 1; b <= N; b++)
for (int c = 1; c <= N; c++)
for (int d = 1; d <= N; d++)
isMove[a][b][c][d] = false;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[r][c] != '.') continue;
for (int i = 0; i < 4; i++)
{
for (int jump = 1; jump <= 5; jump++)
{
int nr, nc;
nr = r + (dr[i] * jump);
nc = c + (dc[i] * jump);
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
if (MAP[nr][nc] == '#') break;
if (MAP[nr][nc] == 'S') continue;
isMove[r][c][nr][nc] = true;
}
}
}
}
}
주어지는 여행정보는 query에 저장한다.
struct QUERY
{
int r1;
int c1;
int r2;
int c2;
};
QUERY query[1000 + 50];
우선순위 큐는 FROG 구조체로 만들면 된다.
struct FROG
{
int r;
int c;
int jump;
int value;
};
FROG heap[50 * 50 * 5];
int hn;
네 방향 좌표는 다음 배열로 처리한다.
// ↑, →, ↓, ←
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
input은 다음과 같다.
void input()
{
scanf("%d", &N);
for (int r = 1; r <= N; r++)
scanf("%s", &MAP[r][1]);
scanf("%d", &Q);
for (int q = 0; q < Q; q++)
scanf("%d %d %d %d", &query[q].r1, &query[q].c1, &query[q].r2, &query[q].c2);
}
main에서 입력을 받고, isMove 함수를 전처리하고 개구리를 움직이면 된다.
int main()
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
makeIsMove();
simulate();
}
return 0;
}
시뮬레이션에서는 시작 좌표와 도착 좌표를 dijkstra 함수에 넘겨주고 결과를 출력하였다.
void simulate()
{
for (int q = 0; q < Q; q++)
{
int r1, c1, r2, c2;
r1 = query[q].r1;
c1 = query[q].c1;
r2 = query[q].r2;
c2 = query[q].c2;
printf("%d\n", dijkstra(r1, c1, r2, c2));
}
}다익스트라
먼저 dist를 INF로 초기화한다.
for (int jump = 1; jump <= 5; jump++)
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
dist[jump][r][c] = INF;
시작 위치에서 개구리의 점프력은 1이므로 dist[1][sr][sc]를 0으로 초기화한다.
dist[1][sr][sc] = 0;
현재 시작 위치와 jump, 비용(value)을 heap에 추가한다.
push({ sr, sc, 1, 0 });
이제 heap이 빌 때까지 거리를 갱신하면 된다.
while (hn)
{
FROG tmp = pop();
// 1. 점프
...
// 2. 점프력 증가 후 이동
...
// 3. 점프력 감소 후 이동
...
}
pop된 개구리에 대해 4방향 좌표를 체크해서 거리를 벗어나거나 움직일 수 없는 경우(check() == false)는 넘어간다.
그렇지 않은 경우, dist[jump]를 확인해서 비용을 갱신하면 된다.
// 1. 점프
for (int i = 0; i < 4; i++)
{
int nr, nc;
nr = tmp.r + (dr[i] * tmp.jump);
nc = tmp.c + (dc[i] * tmp.jump);
if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
if (check(tmp.r, tmp.c, nr, nc) == false) continue;
if (dist[tmp.jump][nr][nc] > tmp.value + 1) // 점프에는 1만큼 시간 소요
{
dist[tmp.jump][nr][nc] = tmp.value + 1;
push({ nr, nc, tmp.jump, dist[tmp.jump][nr][nc] });
}
}
점프력 증가는 현재 jump에서 1을 더한 값부터 5까지 증가할 수 있다.
다음 좌표가 이동 가능한 경우, 점프력 증가에 대한 비용(cost)를 계산해서 이동 비용(1)과 함께 dist를 갱신하면 된다.
// 2. 점프력 증가 후 이동
for (int jump = tmp.jump + 1; jump <= 5; jump++)
{
for (int i = 0; i < 4; i++)
{
int nr, nc;
nr = tmp.r + (dr[i] * jump);
nc = tmp.c + (dc[i] * jump);
if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
if (check(tmp.r, tmp.c, nr, nc) == false) continue;
int cost = getCost(tmp.jump, jump);
// 점프력 증가 비용 + 점프 시간 1 소요
if (dist[jump][nr][nc] > tmp.value + cost + 1)
{
dist[jump][nr][nc] = tmp.value + cost + 1;
push({ nr, nc, jump, dist[jump][nr][nc] });
}
}
}
점프력 증가는 1만 가능하기 때문에 비용이 누적되므로 아래와 같이 getCost를 구현할 수 있다.
int getCost(int startJump, int endJump)
{
int cost = 0;
for (int jump = startJump + 1; jump <= endJump; jump++)
cost += (jump * jump);
return cost;
}
점프력을 감소할 경우는 jump를 1부터 현재 점프력에서 1을 뺀 값 만큼 처리하면 된다.
여기서 점프력 감소에 대한 비용은 1이다.
// 3. 점프력 감소 후 이동
for (int jump = 1; jump <= tmp.jump - 1; jump++)
{
for (int i = 0; i < 4; i++)
{
int nr, nc;
nr = tmp.r + (dr[i] * jump);
nc = tmp.c + (dc[i] * jump);
if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
if (check(tmp.r, tmp.c, nr, nc) == false) continue;
// 점프력 감소 시간 1 소요 + 점프 시간 1 소요
if (dist[jump][nr][nc] > tmp.value + 1 + 1)
{
dist[jump][nr][nc] = tmp.value + 1 + 1;
push({ nr, nc, jump, dist[jump][nr][nc] });
}
}
}
다익스트라 종료 후, dist[jump][er][ec]에서 가장 작은 값이 여행에 걸리는 최소시간이 된다.
값이 갱신 되지 않은 경우는 이동 불가능한 경우이기 때문에 -1을 리턴한다.
int answer = getMinDistance(er, ec);
if (answer == INF) return -1;
return answer;
dist[jump][r][c]에서 가장 작은 값은 아래 함수로 찾으면 된다.
int getMinDistance(int r, int c)
{
int min = INF;
for (int jump = 1; jump <= 5; jump++)
if (min > dist[jump][r][c]) min = dist[jump][r][c];
return min;
}전체 코드는 다음과 같다.
#include <stdio.h>
#define MAX (50 + 5)
#define INF (0x7fff0000)
int T;
int N, Q;
char MAP[MAX][MAX];
int dist[5 + 1][MAX][MAX];
bool isMove[MAX][MAX][MAX][MAX];
struct QUERY
{
int r1;
int c1;
int r2;
int c2;
};
QUERY query[1000 + 50];
struct FROG
{
int r;
int c;
int jump;
int value;
};
FROG heap[50 * 50 * 5];
int hn;
FROG pop()
{
int i;
FROG ret, tmp;
ret = heap[1];
heap[1] = heap[hn];
heap[hn--].value = INF;
for (i = 1; i * 2 <= hn;)
{
if (heap[i].value < heap[i * 2].value && heap[i].value < heap[i * 2 + 1].value) break;
else if (heap[i * 2].value < heap[i * 2 + 1].value)
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
i = i * 2 + 1;
}
}
return ret;
}
void push(FROG x)
{
int i;
FROG tmp;
heap[++hn] = x;
for (i = hn; i > 1; i /= 2)
{
if (heap[i / 2].value < heap[i].value) break;
tmp = heap[i];
heap[i] = heap[i / 2];
heap[i / 2] = tmp;
}
}
// ↑, →, ↓, ←
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void input()
{
scanf("%d", &N);
for (int r = 1; r <= N; r++)
scanf("%s", &MAP[r][1]);
scanf("%d", &Q);
for (int q = 0; q < Q; q++)
scanf("%d %d %d %d", &query[q].r1, &query[q].c1, &query[q].r2, &query[q].c2);
}
void printMap() // for debug
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
printf("%c", MAP[r][c]);
putchar('\n');
}
putchar('\n');
}
int getMinDistance(int r, int c)
{
int min = INF;
for (int jump = 1; jump <= 5; jump++)
if (min > dist[jump][r][c]) min = dist[jump][r][c];
return min;
}
void printDistance() // for debug
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[r][c] == '#') printf(" # ");
else if (getMinDistance(r, c) == INF) printf("-1 ");
else printf("%2d ", getMinDistance(r, c));
}
putchar('\n');
}
putchar('\n');
}
bool check(int sr, int sc, int er, int ec)
{
return isMove[sr][sc][er][ec];
}
int getCost(int startJump, int endJump)
{
int cost = 0;
for (int jump = startJump + 1; jump <= endJump; jump++)
cost += (jump * jump);
return cost;
}
int dijkstra(int sr, int sc, int er, int ec)
{
for (int jump = 1; jump <= 5; jump++)
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
dist[jump][r][c] = INF;
dist[1][sr][sc] = 0;
push({ sr, sc, 1, 0 });
while (hn)
{
FROG tmp = pop();
// 1. 점프
for (int i = 0; i < 4; i++)
{
int nr, nc;
nr = tmp.r + (dr[i] * tmp.jump);
nc = tmp.c + (dc[i] * tmp.jump);
if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
if (check(tmp.r, tmp.c, nr, nc) == false) continue;
if (dist[tmp.jump][nr][nc] > tmp.value + 1) // 점프에는 1만큼 시간 소요
{
dist[tmp.jump][nr][nc] = tmp.value + 1;
push({ nr, nc, tmp.jump, dist[tmp.jump][nr][nc] });
}
}
// 2. 점프력 증가 후 이동
for (int jump = tmp.jump + 1; jump <= 5; jump++)
{
for (int i = 0; i < 4; i++)
{
int nr, nc;
nr = tmp.r + (dr[i] * jump);
nc = tmp.c + (dc[i] * jump);
if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
if (check(tmp.r, tmp.c, nr, nc) == false) continue;
int cost = getCost(tmp.jump, jump);
// 점프력 증가 비용 + 점프 시간 1 소요
if (dist[jump][nr][nc] > tmp.value + cost + 1)
{
dist[jump][nr][nc] = tmp.value + cost + 1;
push({ nr, nc, jump, dist[jump][nr][nc] });
}
}
}
// 3. 점프력 감소 후 이동
for (int jump = 1; jump <= tmp.jump - 1; jump++)
{
for (int i = 0; i < 4; i++)
{
int nr, nc;
nr = tmp.r + (dr[i] * jump);
nc = tmp.c + (dc[i] * jump);
if (nr < 1 || nc < 1 || nr > N || nc > N) continue;
if (check(tmp.r, tmp.c, nr, nc) == false) continue;
// 점프력 감소 시간 1 소요 + 점프 시간 1 소요
if (dist[jump][nr][nc] > tmp.value + 1 + 1)
{
dist[jump][nr][nc] = tmp.value + 1 + 1;
push({ nr, nc, jump, dist[jump][nr][nc] });
}
}
}
}
int answer = getMinDistance(er, ec);
if (answer == INF) return -1;
return answer;
}
void makeIsMove()
{
for (int a = 1; a <= N; a++)
for (int b = 1; b <= N; b++)
for (int c = 1; c <= N; c++)
for (int d = 1; d <= N; d++)
isMove[a][b][c][d] = false;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[r][c] != '.') continue;
for (int i = 0; i < 4; i++)
{
for (int jump = 1; jump <= 5; jump++)
{
int nr, nc;
nr = r + (dr[i] * jump);
nc = c + (dc[i] * jump);
if (nr < 1 || nc < 1 || nr > N || nc > N) break;
if (MAP[nr][nc] == '#') break;
if (MAP[nr][nc] == 'S') continue;
isMove[r][c][nr][nc] = true;
}
}
}
}
}
void simulate()
{
for (int q = 0; q < Q; q++)
{
int r1, c1, r2, c2;
r1 = query[q].r1;
c1 = query[q].c1;
r2 = query[q].r2;
c2 = query[q].c2;
printf("%d\n", dijkstra(r1, c1, r2, c2));
}
}
int main()
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
makeIsMove();
simulate();
}
return 0;
}반응형