BOJ 2178 - 미로 찾기

미로찾기(2178)

전체 코드

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

int	**maze, **flag;

typedef struct	_node
{
	int		x, y, cnt;
	struct _node	*next;
}		node;

node	*front, *rear;

void	init_queue(void)
{
	front = (node *)malloc(sizeof(node));
	rear = (node *)malloc(sizeof(node));

	front -> next = rear;
	rear -> next = rear;
}

void	push(int x, int y, int cnt)
{
	node	*new;

	new = (node *)malloc(sizeof(node));
	new -> x = x;
	new -> y = y;
	new -> cnt = cnt;
	if (front -> next == rear)
	{
		front -> next = new;
		new -> next = rear;
		rear -> next = new;
		return ;
	}
	rear -> next -> next = new;
	new -> next = rear;
	rear -> next = new;
}

void	pop(void)
{
	node	*curr;

	curr = front -> next;
	front -> next = curr -> next;
	free(curr);
}

int	BFS(int N, int M)
{
	int cnt = 0;
	push(1 ,1, cnt + 1);
	flag[1][1]++;
	while (front -> next != rear)
	{
		int	buf_x, buf_y;

		buf_x = front -> next -> x;
		buf_y = front -> next -> y;
		cnt = front -> next -> cnt;
		pop();
		if (buf_x == M && buf_y == N)
			break ;
		if (buf_x - 1 >= 1 && !flag[buf_y][buf_x - 1] && maze[buf_y][buf_x - 1])
		{
			push(buf_x - 1, buf_y, cnt + 1);
			flag[buf_y][buf_x - 1]++;
		}
		if (buf_x + 1 <= M && !flag[buf_y][buf_x +1] && maze[buf_y][buf_x + 1])
		{
			push(buf_x + 1, buf_y, cnt + 1);
			flag[buf_y][buf_x + 1]++;
		}
		if (buf_y - 1 >= 1 && !flag[buf_y - 1][buf_x] && maze[buf_y - 1][buf_x])
		{
			push(buf_x, buf_y - 1, cnt + 1);
			flag[buf_y - 1][buf_x]++;
		}
		if (buf_y + 1 <= N && !flag[buf_y + 1][buf_x] && maze[buf_y + 1][buf_x])
		{
			push(buf_x, buf_y + 1, cnt + 1);
			flag[buf_y + 1][buf_x]++;
		}
	}
	return (cnt);
}

int	main(void)
{
	int	M, N;

	init_queue();
	scanf("%d%d", &N, &M);
	maze = (int **)calloc(1, sizeof(int *) * (N + 1));
	flag = (int **)calloc(1, sizeof(int *) * (N + 1));
	for (int i = 0; i <= N; i++)
	{
		maze[i] = (int *)calloc(1, sizeof(int) * (M + 1));
		flag[i] = (int *)calloc(1, sizeof(int) * (M + 1));
	}
	for (int y = 1; y <= N; y++)
	{
		char	buf[101];
		scanf("%s", buf);
		for (int i = 0; i < M; i++)
			maze[y][i + 1] = buf[i] - '0';
	}
	printf("%d\n", BFS(N, M));
	for (int i = 0; i <= N; i++)
	{
		free(maze[i]);
		free(flag[i]);
	}
	free(maze);
	free(flag);
	free(front);
	free(rear);
	return (0);
}

C를 쓰고, 동적할당으로 메모리까지 fit하게 맞추려다보니까 코드가 더러워지는 경향이 없지않은데, 그래도 최대한 가독성 좋게 쓰려함 .. ㅠ

typedef struct	_node
{
	int		x, y, cnt;
	struct _node	*next;
}		node;

Queue의 구조

x와 y의 좌표, 그리고 목적지까지 몇 번 탐색했는지를 담고있는 cnt 변수를 지닙니다.

배열의 할당은 1, 1의 좌표부터 N,M까지 이루어지는 배열이기 때문에 각각 N + 1, M + 1개씩 할당합니다.

int	BFS(int N, int M)
{
	int cnt = 0;
	push(1 ,1, cnt + 1);
	flag[1][1]++;
	while (front -> next != rear)
	{
		int	buf_x, buf_y;

		buf_x = front -> next -> x;
		buf_y = front -> next -> y;
		cnt = front -> next -> cnt;
		pop();
		if (buf_x == M && buf_y == N)
			break ;
		if (buf_x - 1 >= 1 && !flag[buf_y][buf_x - 1] && maze[buf_y][buf_x - 1])
		{
			push(buf_x - 1, buf_y, cnt + 1);
			flag[buf_y][buf_x - 1]++;
		}
		if (buf_x + 1 <= M && !flag[buf_y][buf_x +1] && maze[buf_y][buf_x + 1])
		{
			push(buf_x + 1, buf_y, cnt + 1);
			flag[buf_y][buf_x + 1]++;
		}
		if (buf_y - 1 >= 1 && !flag[buf_y - 1][buf_x] && maze[buf_y - 1][buf_x])
		{
			push(buf_x, buf_y - 1, cnt + 1);
			flag[buf_y - 1][buf_x]++;
		}
		if (buf_y + 1 <= N && !flag[buf_y + 1][buf_x] && maze[buf_y + 1][buf_x])
		{
			push(buf_x, buf_y + 1, cnt + 1);
			flag[buf_y + 1][buf_x]++;
		}
	}
	return (cnt);
}

종료 조건

함수의 종료 조건은 큐가 비어 미로에 출구가 없거나, N, M좌표 (도착점)를 방문하면 종료되도록 조건을 걸어줍니다.

알고리즘

미로 찾기의 로직은 위와 같은데, 시작 값을 queue에 넣고 첫 번째 값도 방문 횟수에 치기 때문에 queue에 1번 방문했음을 기록.

그리고 dequeue를 하여 나온 값을 버퍼에 담고 버퍼의 상하좌우에 인접한 길이 있으며, 동시에 방문하지 않은 모든 값을 queue에 탐색 횟수를 +1 해주며 넣습니다.

이렇게 도착점을 방문한다면 방문한 횟수를 가지고 반복문이 끝나며, 큐에서 최종으로 나온(방문 후) cnt 값을 반환하며 종료됩니다.