2665 - 미로 만들기 + 경로 출력

Explain

문제보기

본 풀이에서는 위 문제에서 결과로 요청한 최소 검은 방의 수 뿐만 아니라 해당결과의 경로까지 출력한다.

Approach

dijkstra algorithm을 활용하여 풀이하였으며

shorter path를 구하기위한 자료구조로써 priority queue를 구현.

자세한 내용은 추후 정리.

Code

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

typedef struct {
    int x;
	int y;
	int px;
	int py;
	int value;
} heapNode;
 

typedef struct {
    heapNode* heap;
    int size;
} PQ;


void insert(heapNode aNode, heapNode* heap, int size) {
    int idx;
    heapNode tmp;
    idx = size + 1;
    heap[idx] = aNode;
    while (heap[idx].value < heap[idx/2].value && idx > 1) {
    tmp = heap[idx];
    heap[idx] = heap[idx/2];
    heap[idx/2] = tmp;
    idx /= 2;
    }
}
 
void shiftdown(heapNode* heap, int size, int idx) {
    int cidx;        
    heapNode tmp;
    for (;;) {
        cidx = idx*2;
        if (cidx > size) {
            break;   
        }
        if (cidx < size) {
            if (heap[cidx].value > heap[cidx+1].value) {
                ++cidx;
            }
        }
        //swap if necessary
        if (heap[cidx].value < heap[idx].value) {
            tmp = heap[cidx];
            heap[cidx] = heap[idx];
            heap[idx] = tmp;
            idx = cidx;
        } else {
            break;
        }
    }
}
 
heapNode removeMin(heapNode* heap, int size) {
    int cidx;
    heapNode rv = heap[1];
    heap[1] = heap[size];
    --size;
    shiftdown(heap, size, 1);
    return rv;
}

void enqueue(heapNode node, PQ *q) {
    insert(node, q->heap, q->size);
    ++q->size;
}
 
heapNode dequeue(PQ *q) {
   heapNode rv = removeMin(q->heap, q->size);
   --q->size;
   return rv; 
}
 
void initQueue(PQ *q, int n) {
   q->size = 0;
   q->heap = (heapNode*)malloc(sizeof(heapNode)*(n+1));
}

void dijikstra();
void print_path();

int** map;
int** visited_map;
int*** path;
int** change;
int N;
FILE *output;

PQ q;

int DIR[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

int main(void)
{
	FILE *file;
	char file_name[255];
	int i,j;
	
	printf("input file name?");
	scanf("%s", &file_name);

	file = fopen(file_name, "r");
	output = fopen("output.txt", "w");

	N = fgetc(file) - '0';

	initQueue(&q, N*N);

	map = (int **)malloc(sizeof(int*) * N);
	path = (int ***)malloc(sizeof(int**) * N);
	visited_map = (int **)malloc(sizeof(int*) * N);
	change = (int **)malloc(sizeof(int*) * N);

	for(i=0;i<N;++i)
	{
		map[i] = (int *)malloc(sizeof(int) * N);
		visited_map[i] = (int *)malloc(sizeof(int) * N);
		change[i] = (int *)malloc(sizeof(int) * N);
		path[i] = (int **)malloc(sizeof(int*) * N);

		for(j=0;j<N;)
		{
			char c = fgetc(file);

			if(c != '\n'){
				path[i][j] = (int *)malloc(sizeof(int) * 2);
				map[i][j] = c - '0';
				visited_map[i][j] = 0;
				change[i][j] = 0;
				j++;
			}
		}
	}

	dijikstra();

	fprintf(output ,"%d\n", change[N-1][N-1]);
	print_path(N-1, N-1);
	fprintf(output ,"%d, %d\n", N, N);

	return 0;
}

void print_path(int x, int y)
{
	int px = path[x][y][0];
	int py = path[x][y][1];

	if(px != 0 || py != 0){
		print_path(px, py);
	}

	fprintf(output, "%d, %d\n", py+1,  px+1);
}

void dijikstra()
{
	heapNode current;
	current.value = current.x = current.y = 0;
	enqueue(current, &q);

	while(q.size != 0)
	{
		int i,j, px = 0, py = 0;
		heapNode temp;
		current = dequeue(&q);
		
		if(visited_map[current.x][current.y] == 1) continue;
		
		visited_map[current.x][current.y] = 1;
		change[current.x][current.y] = current.value;

		path[current.x][current.y][0] =  current.px;
		path[current.x][current.y][1] =  current.py;
		
		for(i = 0 ; i < 4 ; ++i)
		{
			temp.x = current.x + DIR[i][0];
			temp.y = current.y + DIR[i][1];

			if(temp.x < 0 || temp.x >= N || temp.y < 0 || temp.y >= N) continue;
			if(visited_map[temp.x][temp.y] == 1) continue;

			temp.value = current.value;

			if(map[temp.x][temp.y] == 0)
				temp.value++;

			temp.px = current.x;
			temp.py = current.y;

			enqueue(temp, &q);
		}
	}
}

Reference

Dijkstra's algorithm

Priority Queue