[백준 / C언어] 2178번: 미로 탐색

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

2178번: 미로 탐색

 

난이도: solved.ac 실버 1

 

 

BFS를 알고 있다면 쉽게 풀 수 있는 문제다

 

먼저 map에 입력을 받아주고, visited라는 2차원 배열을 통해 해당 index의 위치를 방문했는지 표시하며

 

이때 표시는 출발 위치로부터 떨어진 거리로 표시한다

 

문제에서 출발 위치와 도착 위치도 칸을 세야 한다고 했으므로 visited를 1부터 시작했다

 

Ex.

visited[0][0] = 1

visited[0][1] = 2

...

 

내가 말을 잘 못해서 괜히 어렵게 설명했는데, 이동할 때마다 숫자를 1씩 늘려가며 visited에 적어준다는 것이다

 

예제 입력 4

 

아래는 예제 입력 4를 입력하면 visited가 어떻게 되는지 나타낸 건데 참고하면 좋을 것 같다

 

BFS를 돌리면 더 이상 탐색할 곳이 없을 때까지 탐색을 반복하는데

 

그래서 실제로는 깊이가 14인 곳까지 탐색을 한다

 

하지만 문제에서는 (N - 1, M - 1) 위치까지 가는 최단 거리를 물으므로

 

13을 출력하게 된다 

 

 

BFS는 큐(Queue)를 이용해 구현하는데, 이 문제에서는 큐에 2차원 배열의 각 행, 열의 index를 담아야 하므로

 

struct를 이용해 구조체 배열로 큐를 만들어주었다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int map[101][101];
int visited[101][101];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

typedef struct _Queue {
	int v_x;	// visited x
	int v_y;	// visited y
} Queue;


int main() {
	int N, M, i, j;
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
			scanf("%1d", &map[i][j]);

	Queue queue[10000];

	int head = -1, rear = -1;
	int x = 0, y = 0;

	rear++;
	queue[rear].v_x = x;
	queue[rear].v_y = y;
	visited[x][y] = 1;

	while (head < rear) {
		head++;
		x = queue[head].v_x;
		y = queue[head].v_y;
		for (i = 0; i < 4; i++) {
			int dir_x = dx[i];
			int dir_y = dy[i];
			if (!visited[x + dir_x][y + dir_y] && map[x + dir_x][y + dir_y]) {
				visited[x + dir_x][y + dir_y] = visited[x][y] + 1;
				rear++;
				queue[rear].v_x = x + dir_x;
				queue[rear].v_y = y + dir_y;
			}
		}
	}

	printf("%d", visited[N - 1][M - 1]);
	return 0;
}