[백준] 2178 미로 탐색 - C

 

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

 

---

 

본격적으로 BFS에 대해 공부하기 위해 대표적인 BFS문제를 찾아 풀어보려 한다..

 

BFS는 너비우선탐색으로, 인접한 노드들을 차례대로 모두 탐색한다.

또한 시작 노드부터 목표 노드까지의 최단거리 경로를 보장한다. (무가중 그래프)

출처: 나무위키-너비우선탐색

 

이 그림이 이해에 굉장한 도움을 주었다.

BFS는 탐색을 위해 큐라는 자료구조를 사용하니 큐를 모른다면 공부하고 오도록 하자.

---

 

문제를 풀어보자.

N * M 크기의 배열에서 (N, M)의 위치로 이동하기 위해 거쳐야 하는 최소 칸 수를 출력한다.

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

#define MAX 100
int n, m;
int maze[MAX][MAX];
int dist[MAX][MAX];

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

typedef struct {
	int x;
	int y;
}Point;

typedef struct {
	Point queue[MAX * MAX];
	int front;
	int rear;
}Queue;

void enqueue(Queue* q, int x, int y);
Point dequeue(Queue* q);
int is_empty(Queue* q);

void bfs(int x, int y);

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		char buf[MAX];
		scanf("%s", buf);
		for (int j = 0; j < m; j++) {
			maze[i][j] = buf[j] - '0';
		}
	}
	bfs(0, 0);
	printf("%d", dist[n - 1][m - 1]);
	return 0;
}
void bfs(int x, int y) {
	Queue q = { .front = 0, .rear = 0 };
	enqueue(&q, x, y);
	dist[y][x] = 1;
	while (!is_empty(&q)) {
		Point cur = dequeue(&q);
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
				if (!dist[ny][nx] && maze[ny][nx] == 1) {
					dist[ny][nx] = dist[cur.y][cur.x] + 1;
					enqueue(&q, nx, ny);
				}
			}
		}
	}
}
void enqueue(Queue* q, int x, int y) {
	q->queue[q->rear].x = x;
	q->queue[q->rear].y = y;
	q->rear++;
}
Point dequeue(Queue* q) {
	return q->queue[q->front++];
}
int is_empty(Queue* q) {
	return q->front == q->rear;
}

---

코드 설명

• 변수
  • maze[][] - 입력받은 미로를 저장할 이차원 배열이다.
  • dist[][] - 미로의 해당 위치에 몇번만에 도달했는지 기록하는 이차원 배열이다.
  • dx[], dy[] - 이동방향을 나타낸다.
  • Point - x, y를 멤버로 가지는 구조체이다. 미로가 이차원 배열이기 때문에 x, y로 표현해야 해서 편의를 위해 만들었다. 타입으로 선언했다.
  • Queue - 자료구조 큐를 구현한 구조체이다. Point형 배열 queue와 큐에 필요한 front, rear를 멤버로 가진다. queue는 최악의 경우 미로의 모든 칸이 방문 대상이 될 수 있기 때문에 넉넉히 MAX * MAX로 선언한다.
• bfs 함수
  • 큐 q를 선언하고 시작지점(0, 0)을 큐에 넣는다. 그리고 dist의 해당 위치를 1로 바꾼다. (시작 위치도 칸 수에 포함해서 세기 때문)
  • 큐가 빌 때 까지 반복한다.
  • 현재 위치를 나타내는 Point형 변수 cur을 선언하고 큐에서 값을 하나 빼 와 저장한다.
  • 이동할 수 있는 방향이 네 방향이기 때문에 4번 반복한다.
  • 다음에 이동할 위치의 x, y를 nx, ny로 선언한다.
  • 선언한 nx, ny가 배열 범위 내에 있는지 검사한 후, 미로의 해당 위치가 1이고(이동할 수 있는 칸이고), 이전에 방문했던 칸인지 검사한다. (방문했다면 다시 접근해선 안된다.)
  • 조건을 모두 통과하면 dist의 해당 위치를 시작부터 해당 위치까지의 거리(이전 위치의 거리 + 1)로 저장하고, 해당 위치를 큐에 넣음으로써 다음 탐색을 진행할 수 있게 한다.

---

 

생각보다 금방 감을 잡을 수 있었다.

---