미로 탐색 / 백준 (Baekjoon) / 2178

---

미로 탐색 / 백준 (Baekjoon) / 2178

** 여기서 다루는 알고리즘 문제는 저의 창작 문제가 아닐 경우, 저작권 관련 문제를 방지하고자, 문제의 대략적인 설명 및 요구사항만 소개하고 있습니다. 

** 이 공간에서 공유되는 풀이 및 Source code는 제 개인의 학습 목적이며, 당연히 최선의 정답이 아닙니다. 

** 혹시 더 나은 방법이나 아이디어가 있으신 경우에는, 댓글에 의견을 공유해주시면 감사하겠습니다.

** Source code는 C 언어로 작성되었습니다.

---

알고리즘 분류 및 개요

- 너비 우선 탐색 (BFS, Breadth First Search)
  

Input / output

- 입력

 첫째 줄에 두 정수 N, M(2≤N, M≤100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

- 출력

 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

주의 사항

• 전형적인 BFS 문제로, 가중치가 없는 최단 거리를 구하는 문제입니다. 

• 따라서, 이 문제를 DFS로 풀 경우 시간 초과에 걸릴 수 있습니다.

• 문자열 입력을 string으로 받을 때는, 항상 마지막 Buffer 공간에 null이 존재함을 인지하여, buffer를 한 칸 더 크게 잡아야 합니다.    (아래 코드에서는 편의상 char형으로 문자열을 배열에 바로 할당하고 있으므로, 101로 MAX_INPUT_SIZE를 선언할 필요는 없습니다.)

• BFS에서는 공통적으로,
1. 방문한 node가 재방문하지 않도록 visit flag를 세워서 queue가 full이 되지 않도록 관리되어야 하고,
2. 요구 사항에 특별한 제한이 없을 경우, 네 방향(또는 여덟방향) 으로 모두 node check가 되어야 합니다.

• 이 문제의 경우, Queue에 담긴 마지막 노드까지 처리되지 않고, BFS가 종료되는 케이스가 있을 수 있습니다. 이에 대한 예시는 다음과 같습니다.

6 5

11111

10001

10101

10111

10000

11111

>> 10

 

 

NOTE :

 아래에 Test input file을 첨부하였으니, 본인의 풀이가 틀렸을 경우 생각하지 못했던 Corner case가 있는지 확인해 보시기 바랍니다.

 

 

Source code

---

///////////////////////////////////////////////
// - Backjoon 2178 : 미로 탐색
// - https://www.acmicpc.net/problem/2178
///////////////////////////////////////////////

#include 

typedef unsigned int	(u32);
typedef unsigned short  (u16);
typedef unsigned char	(u8);

typedef signed int		(s32);
typedef signed short	(s16);
typedef signed char		(s8);

#define	MAX_INPUT_SIZE	(101)

// -- Global variables

// Input
u32 g_width, g_height;
u8 input_buf[MAX_INPUT_SIZE][MAX_INPUT_SIZE];

// BFS - Queue
typedef struct _tag_POSITION {
	u32 pos_x;
	u32 pos_y;
}__POS;

u32 Q_front_flag;
u32 Q_rear_flag;

__POS Queue[MAX_INPUT_SIZE * MAX_INPUT_SIZE];

#define ENQUEUE(x, y, Q_pos)	do { Queue[Q_pos].pos_x = (u32)x; Queue[Q_pos].pos_y = (u32)y; Q_pos++; } while(0)
#define DEQUEUE(x, y, Q_pos)	do { x = Queue[Q_pos].pos_x; y = Queue[Q_pos].pos_y; Q_pos++; } while(0)

// BFS - visit buf
u8 visit_buf[MAX_INPUT_SIZE][MAX_INPUT_SIZE];

// Result
u32 g_opt_length;

static void SetInputBuffer( void )
{
	u32 i, j;

	scanf("%d %d", &g_height, &g_width);

	for (i = 0; i < g_height; i++)
	{
		for (j = 0; j < g_width; j++)
		{
			scanf(" %c", &input_buf[i][j]);
		}
	}
}

static __inline void CheckUnvisitedNode( s32 pos_x, s32 pos_y )
{
	if ((visit_buf[pos_y][pos_x] == 0) && (input_buf[pos_y][pos_x] == '1'))
	{
		ENQUEUE(pos_x, pos_y, Q_rear_flag);
		visit_buf[pos_y][pos_x] = 1;
	}
}

static void BFS( s32 pos_x, s32 pos_y )
{
	if (pos_y + 1 < g_height)	CheckUnvisitedNode( pos_x, pos_y + 1 );
	if (pos_y >= 1)				CheckUnvisitedNode( pos_x, pos_y - 1 );
	if (pos_x + 1 < g_width)	CheckUnvisitedNode( pos_x + 1, pos_y );
	if (pos_x >= 1)				CheckUnvisitedNode( pos_x - 1, pos_y );
}

s32 main(void)
{
	u32 bound_for_next_step = 0;

	SetInputBuffer();

	ENQUEUE(0, 0, Q_rear_flag);
	visit_buf[0][0] = 1;

	bound_for_next_step = Q_rear_flag;

	do {
		u32 curr_pos_x, curr_pos_y;

		DEQUEUE(curr_pos_x, curr_pos_y, Q_front_flag);
		BFS(curr_pos_x, curr_pos_y);

		if ((curr_pos_x == (g_width - 1)) &&
		(curr_pos_y == (g_height - 1)))
		{
			break;
		}

		if (Q_front_flag == bound_for_next_step)	
		{
			bound_for_next_step = Q_rear_flag;
			g_opt_length++;
		}

	} while (Q_front_flag < Q_rear_flag);
	
	printf("%d\n", g_opt_length + 1);

	return 0;
}

---

난이도 / 중요도 / 재시도

  ★★★★☆ / ★★★☆☆ / x 4

출처 / 관련 링크

- Baekjoon online judge : https://www.acmicpc.net/problem/2178

- BFS Algorithm 소개 : http://jayce-with.tistory.com/9

Test input file

input_sample.txt