[백준 2178] 미로 탐색

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

2178번: 미로 탐색

#include <cstdio>
#include <iostream>
#include <queue>
int N, M;	// 행, 열
char board[100 + 10][100 + 10];
bool visited[100 + 100][100 + 100];

struct _st
{
	int a;
	int b;
	int t;
};

std::queue<_st> Q;

void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%s", &board[i][1]);	// (1, 1)부터 시작
	}
}

int maze(void)
{
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q.push({ 1, 1, 1 });	// (1, 1) 칸도 카운팅
	visited[1][1] = true;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int na = data.a + dir_x[p];
			int nb = data.b + dir_y[p];
			int ntime = data.t + 1;

			if (na == N && nb == M) return ntime;

			if (na < 1 || na > N || nb < 1 || nb > M || visited[na][nb] == true || board[na][nb] == '0') continue;
			Q.push({ na, nb, ntime });
			visited[na][nb] = true;
		}
	}
}


int main()
{
	input();
	int ans = maze();
	printf("%d", ans);
	return 0;
}

 

이 문제는 전형적인 BFS 문제이다. 

(1, 1)에서 (N, M)까지 가는 "최소 칸 수"를 묻고 있기 때문이다. 

Queue 자료구조를 사용한 이유는 상태를 저장하기 위함이다. 먼저 저장시킨 상태를 먼저 꺼내어 사용함으로써 동일한 뎁스의 좌표를 먼저 탐색하도록 구현하였다. 

 

// input( ) 함수

(1, 1)가 시작점이므로 board 행과 열의 두번째 인덱스부터 시작해주기 위해 루프를 1부터 돌렸고, board[i][1] 부터 받았다. 이때 정수"%d"로 받을 수 없는 이유는 각각의 숫자가 붙어서 입력되기 때문이다(공백으로 구분되어 입력받을 때만 가능). 그래서 문자열"%s"로 받아주어야 한다. 

 

 

// maze( ) 함수

초기 세팅은 다음과 같다. 

현재 위치에서 "한 칸" 단위로 갈 수 있는 위치를 탐색하기 위해 방향벡터(dir_x, dir_y)를 두었다.

탐색의 시작인 (1, 1)위치를 큐에 넣고, 방문 배열인 visited의 (1, 1)위치를 true로 바꾸어 표시한다. 전역변수로 bool 배열을 만들면 디폴트는 false이기 때문이다. 

 

그리고 큐에 원소가 없을 때 까지 반복문을 돌리면서 다음과 같은 과정을 수행한다. 

구조체 data에 큐에 가장 상단에 있는(지금 당장 탐색할) 데이터를 저장한다. 그리고 해당 원소를 큐에서 꺼내준다. 

다음으로 4 방향을 돌면서 새로운 좌표 (na, nb)가 (N, M)이면 걸린시간(ntime)을 리턴한다. 만약 좌표를 전진하면서 영역을 벗어나거나, 이미 방문한 좌표이거나, 벽을 만나면 큐에 원소를 푸시하지 않고 지나간다. 둘 다 아니라면 큐에 새로운 좌표를 추시하고, 방문배열을 true로 바꾸어 방문을 표시한다.