백준 2178 - 미로 탐색

문제는 링크로 첨부합니다.

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

2178번: 미로 탐색

출발지점 0,0 에서 N,M으로 가는 최단거리를 구하는 문제입니다. 단순히 bfs를 활용해서 탐색하다가 도착지점을 만났을때 종료하고 거리를 구하려 했지만 최악의 경우 모든 지점을 탐색하게 되어 시간초과가 발생하였습니다.

그래서 큐에 넣는 지점마다 출발지점으로부터의 거리를 저장하고 우선순위 큐를 이용하여 거리가 짧은것을 우선으로 탐색하도록 하였습니다. 하지만 이 역시 최악의 경우 한방향으로 가다가 반대로 꺽이는 부분이 발생할 경우에도 모두 탐색하게되어 시간초과가 발생하였습니다. 예를 들면

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

다음과 같은 미로의 경우 꺽여 다시 안쪽으로 들어가는 길이 있을 때 곧바로 가는 방향하고 출발지점부터의 거리는 같기때문에 모두 탐색하게 됩니다. 그래서 더 시간을 줄이기 위해 탐색노드에 출발지점에서의 거리와 도착지점까지의 예상 최단경로의 합을 기준으로 우선순위 큐를 사용하였습니다. 그렇게 하면 꺾여들어가는 순간 도착지점에서 거리가 멀어지기 때문에 꺾여들어가는 경로를 탐색하지 않게됩니다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <queue>
 
using namespace std;
 
#define MAX 101
 
int maze[MAX][MAX];
int visit[MAX][MAX];
int N, M, result;
 
int index[4][2] = { {1,0}, {-1,0}, {0,1},{0,-1} };
 
typedef struct NODE {
	int dis;
	int weight;
	int n;
	int m;
}node;
 
struct compare {
	bool operator()(node a, node b) {
		return a.dis + a.weight > b.dis + b.weight;
	}
};
 
void maze_runner() {
	priority_queue<node, vector<node>, compare > q;
	node cur_node;
	q.push(node{ 1 , (M - 0) + (N - 0),  0, 0 });
	while (q.empty() == false) {
		cur_node = q.top();
		//printf("%d %d %d\n", cur_node.dis, cur_node.n, cur_node.m);
		if (cur_node.n == N - 1 && cur_node.m == M - 1) {
			result = cur_node.dis;
			break;
		}
		visit[cur_node.n][cur_node.m] = 1;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nidx = cur_node.n + index[i][0];
			int midx = cur_node.m + index[i][1];
			if (nidx < 0 || nidx >= N || midx < 0 || midx >= M) {
				continue;
			}
			if (visit[nidx][midx] == 0 && maze[nidx][midx]) {
				q.push( node{ cur_node.dis + 1 , (N-nidx) + (M-midx) , nidx, midx });
			}
		}
	}
}
int main()
{
	scanf("%d %d", &N, &M);
	getchar();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			char info;
			scanf("%c", &info);
			maze[i][j] = info - '0';
		}
		getchar();
	}
 
	maze_runner();
 
	printf("%d", result);
}

*알고보니 이런 문제의 경우 A*알고리즘을 활용하면 가장 빠르게 해결할 수 있는 것이었습니다.