[알고리즘] 백준 온라인 저지 BOJ 2178 미로탐색

2178번 미로탐색

문제 해석

---

추석인데 할게 없으니, 알고리즘 하나 풀어보자구요!

NxM행렬이 있습니다. N은 행의 수, M은 열의 수인데, 1은 통과 가능한 구역, 0은 통과하지 못하는 공간이라고 문제 설명에서 말합니다.

(1,1)부터 시작해 (N,M)까지 오는데, 가장 적게 1을 통과하는 수를 구하는 게 문제의 답입니다.

아래처럼 빨간 색으로 된 1을 통과하는 게 답이 되겠고, 15가 답이 됩니다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

물론 답은 여러가지가 있을 수도 있겠죠?

위에 빨간점대로 이동하지 않고도 녹색점을 거쳐서 오는 경우도 가능한데, 어차피 답은 똑같다라는 점입니다.

한칸 띄어서 정수형으로 주지 귀찮게

제약 조건

---

N과 M 둘 다 2이상 100이하가 되겠습니다. 

풀이

---

음...

최소라... 

일단 어떤 지도같은 것을 주고, "최단거리를 구하라" 라는 문제는 BFS로 풀어볼만 합니다. BFS가 최단 거리를 구하는데 안성맞춤이거든요. 어떤 정점이 있을때 그 주위에 있는 정점들만 우선적으로 돌기 때문이지요.

그리고 N과 M, 모든 점을 계산했을 때 10000개 이하가 되니까 Queue에 담기도 충분합니다.

BFS https://reakwon.tistory.com/7?category=300867

우선 어떤 점 (y,x)가 있을때, 사방에 1인 녀석들을 일단 찾습니다. 그놈들이 그래프의 정점 중 다음에 방문해야할 후보들에 속하거든요.

그렇다면 상하좌우이니까 (y, x-1), (y, x+1), (y+1, x), (y-1, x)로 주변 정점들을 찾고 이미 방문된 정점이라면 그냥 skip하면 되겠네요.

#include <cstdio>
#include <queue>
#include <string>
#include <string.h>

using namespace std;

int n, m;
bool visited[101][101];
char map[101][101];

struct Point {
	int x, y;
	Point(int _y, int _x) {
		x = _x; y = _y;
	}
};

queue<Point> q;

void pushQ(int y, int x) {

	if (y >= n || x >= m || y<0 || x<0 || visited[y][x] || map[y][x] == '0') return;
	q.push(Point(y, x));

	visited[y][x] = true;
}

int bfs() {

	pushQ(0, 0);
	int count = 1;
	while (!q.empty()) {

		int size = q.size();

		for (int i = 0; i<size; i++) {
			Point here = q.front();
			q.pop();

			if (here.y == n - 1 && here.x == m - 1) return count;

			pushQ(here.y + 1, here.x);
			pushQ(here.y - 1, here.x);
			pushQ(here.y, here.x + 1);
			pushQ(here.y, here.x - 1);
		}
		count++;
	}
	return count;
}

int main() {
	scanf("%d %d", &n, &m);

	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++)
		scanf("%s", map[i]);

	printf("%d\n", bfs());
	return 0;
}

위 코드는 단순하게 (0,0) (문제에서는 1,1라고 했지만, 배열은 0,0부터 첫번째 요소이기 때문에)부터 시작해서 (n-1, m-1)( 역시 배열의 가장 마지막 요소는 n-1, m-1)까지 문자열로 입력을 받고,  bfs를 돕니다.

bfs에서는 우선 시작 정점(0,0)을 큐에 집어 넣습니다. 그 후에 bfs의 size를 호출해 포문을 돌고 그 상하좌우의 정점을 집어 넣게 되는 겁니다. 주의해야할 점은 for루프 조건문에서 직접적으로 q.size()를 호출하면 안된다는 점입니다. for루프 안에서 q에 push되므로 for문을 한번 돌때마다 q.size()가 유동적으로 바뀌게 됩니다.

                int size = q.size();

		for (int i = 0; i<size; i++) {
			Point here = q.front();
			q.pop();

			if (here.y == n - 1 && here.x == m - 1) return count;

			pushQ(here.y + 1, here.x);
			pushQ(here.y - 1, here.x);
			pushQ(here.y, here.x + 1);
			pushQ(here.y, here.x - 1);
		}
		count++;

그렇게 for문을 한 번 돌면 그 주위에 있는 정점 한번을 탐색한 것이니까 count를 하나 증가시켜 주고요. 만약 n-1, m-1 정점까지 도달했다면 바로 이 count를 return하게 되면 몇 번만에 (n-1, m-1)까지 도달했는지 알 수 있습니다.

pushQ함수는 조건에 맞지 않는 정점은 그냥 지나쳐 버립니다.

조건에 맞지 않는 정점이라는 것은 범위밖의 정점( 0보다 작거나 n또는 m보다 큰 정점), 이미 방문된 정점, 또는 0인 정점을 말하는 것이죠.

방문해야 할 정점이라면 큐에 push하고 방문되었다는 표시만 해주는 아주 단순한 함수입니다. visited[y][x] = true가 바로 방문되었다는 표시를 해주는 작업이랍니다.

단순하긴 하지만 이 함수가 없다면 for루프 안에 일일히 if문으로 검사를 해주어야하는 뻘짓을 하게 될겁니다.

void pushQ(int y, int x) {

	if (y >= n || x >= m || y<0 || x<0 || visited[y][x] || map[y][x] == '0') return;
	q.push(Point(y, x));

	visited[y][x] = true;
}

그리고 또 한가지는 pushQ를 총 4번 호출하죠?

for문으로 돌릴 수 있으나, 거기까지 생각하면서 귀찮게 코딩 안하잖아요 우리는...

그냥 짧은거는 복붙합시다... 티도 안나요.

점(point)을 조금 편하게 관리하게 위해서 Point라는 구조체를 사용했습니다.

뭐... 사용하지 않고 그냥 배열로만 해도 상관없구요.

십쥬?