BOJ 1261 : 알고스팟

알고리즘 문제 전체 링크

 

https://www.acmicpc.net/problem/1261

 

※ 다익스트라를 이용하여 최단 경로 이동하기는 유니티에서 확인할 수 있다.

 

BOJ 11779 : 최소비용 구하기 2의 다익스크라(데이크스트라) 알고리즘을 2차원 배열에서 사용하면 된다.

2차원 배열의 각 인접한 노드는 dr, dc 배열로 탐색한다.

int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };

 

그리고 벽(1)이 비용이 된다.

int MAP[110][110];

 

거리를 저장할 2차원 배열과 방문 여부를 체크하는 배열, 그리고 최소 힙을 만든다.

int distance[110][110];
int visit[110][110];

typedef struct st2
{
	int r;
	int c;
	int value;
}HEAP;

HEAP heap[110 * 110];
int hn;

 

다익스트라 알고리즘을 사용하기 위해 distance 배열을 큰 값으로 초기화하고, 

(1, 1)부터 시작하므로 비용이 0이 되게 한 후, heap에 넣으면 된다.

dr, dc 배열을 이용해 네 방향 탐색을 하며 도착지점까지 최소 거리를 찾으면 된다.

int main()
{
	...
    
	for (int i = 1; i <= N; i++)
		for (int k = 1; k <= M; k++)
			distance[i][k] = 0x7fff0000;

	distance[1][1] = 0;

	push(heap, hn, { 1, 1, 0 });

	while (hn)
	{
		HEAP tmp;

		tmp = pop(heap, hn);

		if (visit[tmp.r][tmp.c]) continue;
        
		visit[tmp.r][tmp.c] = 1;

		for (int i = 0; i < 4; i++)
		{
			int nr = tmp.r + dr[i];
			int nc = tmp.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > M) continue;

			if (distance[nr][nc] > distance[tmp.r][tmp.c] + MAP[nr][nc])
			{
				distance[nr][nc] = distance[tmp.r][tmp.c] + MAP[nr][nc];
				push(heap, hn, { nr, nc, distance[nr][nc] });
			}
		}
	}

	printf("%d\n", distance[N][M]);

	return 0;
}

 

최종 코드는 다음과 같다.

#include <stdio.h>

int N, M;
int MAP[110][110];

int distance[110][110];
int visit[110][110];

typedef struct st2
{
	int r;
	int c;
	int value;
}HEAP;

HEAP heap[110 * 110];
int hn;

int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };

HEAP pop(HEAP *heap, int& hn)
{
	HEAP ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].value = 0x7fff0000;

	for (int 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(HEAP *heap, int& hn, HEAP x)
{
	HEAP tmp;
	heap[++hn] = x;

	for (int 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 main()
{
	scanf("%d %d", &M, &N);

	for (int i = 1; i <= N; i++)
		for (int k = 1; k <= M; k++)
			scanf("%1d", &MAP[i][k]);

	for (int i = 1; i <= N; i++)
		for (int k = 1; k <= M; k++)
			distance[i][k] = 0x7fff0000;

	distance[1][1] = 0;

	push(heap, hn, { 1, 1, 0 });

	while (hn)
	{
		HEAP tmp;

		tmp = pop(heap, hn);

		if (visit[tmp.r][tmp.c]) continue;
        
		visit[tmp.r][tmp.c] = 1;

		for (int i = 0; i < 4; i++)
		{
			int nr = tmp.r + dr[i];
			int nc = tmp.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > M) continue;
            
			if (distance[nr][nc] > distance[tmp.r][tmp.c] + MAP[nr][nc])
			{
				distance[nr][nc] = distance[tmp.r][tmp.c] + MAP[nr][nc];
				push(heap, hn, { nr, nc, distance[nr][nc] });
			}
		}
	}

	printf("%d\n", distance[N][M]);

	return 0;
}