본문 바로가기
알고리즘/[ADV] 삼성 SW 역량 테스트 A형

[코드트리] 개구리의 여행 (삼성 SW 역량테스트 2025 상반기 오전 2번, B형)

by 피로물든딸기 2025. 5. 1.
반응형

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

삼성 B형 전체 링크

 

2022 하반기 이후 문제 풀이 시간이 3시간  4시간으로 변경,

A형 1문제 + B형 문제 1문제가 출제됩니다.

 

참고 

- B형 필수 : 우선순위 큐 Priority Queue

- BOJ 11779 : 최소비용 구하기 2

- BOJ 6593 : 상범 빌딩

 

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;
}
반응형

댓글