[코딩테스트C++] 미로 탐색

오늘의 문제

미로 탐색

나의 풀이

#include <iostream>
#include <queue>
#define MAX 100
using namespace std;

// 미로 탐색
int maze[MAX][MAX] ={0, };
bool check[MAX][MAX] = {false, };
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int N, M;
int solution(){
    int answer = 0;
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(0, 0), 1));
    int n, m;
    check[0][0] = true;
    while(!q.empty()){
        n = q.front().first.first;
        m = q.front().first.second;
        answer = q.front().second;
        q.pop();
        if(n == N-1 && m == M-1){
            return answer;
        }
        for(int i=0;i<4;i++){
            int nextN = n + dx[i];
            int nextM = m + dy[i];
            if(nextN <0 || nextN >=N || nextM <0 || nextM >=M)
                continue;
            if( !check[nextN][nextM] && maze[nextN][nextM] == 1){
                check[nextN][nextM] = true;
                q.push(make_pair(make_pair(nextN, nextM), answer +1));
            }
        }
    }
    return answer;
}

풀이 법

• 미로찾기를 BFS로 풀어야하는 이유는 DFS로 문제를 풀 경우, 경우의수가 너무 많아진다. 또한 마지막 지점을 지나는 경로의 최소값을 구해야하므로 시간초과가 남.
• BFS를 통해 찾으면, 최초로 도착하는 경로가 정답 => 경우의수를 확 줄일 수 있음
• 또한 visit 배열을 잘못 체크했다가 시간초과가 났었다. 다음으로 갈 지점의 방문을 체크해야 시간초과가 나지 않는다.

모범 답안

#include <stdio.h>

typedef struct _Coord {
	int x, y;
} Coord;

int main(void)
{
	char map[100][101];
	int N, M, i;

	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
		scanf("%s", map[i]);

	Coord queue[10000];
	int front, back, end;
	queue[0].x = 0;
	queue[0].y = 0;
	map[0][0] = '0';
	front = 0; back = 1;
	int count = 0;
	Coord cur = { 0, 0 };

	while (front != back)
	{
		count++;
		end = back;
		while (front != end)
		{
			cur = queue[front++];

			if (cur.x == M - 1 && cur.y == N - 1)
				goto out;

			if (cur.x != 0 && map[cur.y][cur.x - 1] == '1')
			{
				queue[back].x = cur.x - 1;
				queue[back++].y = cur.y;
				map[cur.y][cur.x - 1] = '0';
			}
			if (cur.x != M - 1 && map[cur.y][cur.x + 1] == '1')
			{
				queue[back].x = cur.x + 1;
				queue[back++].y = cur.y;
				map[cur.y][cur.x + 1] = '0';
			}
			if (cur.y != 0 && map[cur.y - 1][cur.x] == '1')
			{
				queue[back].x = cur.x;
				queue[back++].y = cur.y - 1;
				map[cur.y - 1][cur.x] = '0';
			}
			if (cur.y != N - 1 && map[cur.y + 1][cur.x] == '1')
			{
				queue[back].x = cur.x;
				queue[back++].y = cur.y + 1;
				map[cur.y + 1][cur.x] = '0';
			}
		}
	}

out:
	printf("%d", count);
}

배울 점