[알고리즘/문제풀이][BOJ 2178번] 미로 탐색

미로 탐색 문제는 노드 사이의 최단 거리를 구하는 문제이다. 노드 간 최단 거리를 구할 때는 BFS를 사용할 수 있다. BFS 알고리즘 특성상 그래프에서 노드간 최단 거리를 찾기 때문이다.

BFS의 일반형에서 약간의 변형을 통해 코드를 구현할 수 있다.

BFS 일반형은 다음 게시물에서 참고할 수 있다.

2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

[알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

문제에 대해 작성한 코드는 다음과 같다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com/

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

int map[120][120];
int wp, rp;

struct Queue {
	int x;
	int y;
	int time;
};

struct Queue queue[20000];
struct Queue temp;

void enqueue(int x, int y, int time) {
	queue[wp].x = x;
	queue[wp].y = y;
	queue[wp].time = time;
	wp++;
}

struct Queue dequeue() {
	return queue[rp++];
}

int empty() {
	return wp == rp;
}

int main(void) {
		scanf("%d %d", &N, &M);

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

		enqueue(1,1,1);
		map[1][1] = 2;

		while (!empty()) {
			temp = dequeue();
			if ((temp.x == M) &&( temp.y == N)) {
				printf("%d\n", temp.time);
				break;
			}

			for (int k = 0; k < 4; k++) {
				int nx = temp.x + dx[k];
				int ny = temp.y + dy[k];
				if (nx < 1 || nx > M) continue;
				if (ny < 1 || ny > N) continue;
				if (map[ny][nx] != 1) continue;
				enqueue(nx, ny,temp.time+1);
				map[ny][nx] = 2;
			}
		}

		return 0;
}

 

문제의 지문은 다음의 링크에서 확인할 수 있다.

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