[ DFS | BFS ] 미로 탈출

난이도 : 중하 풀이시간 : 30분 시간제한 : 1초 

[ DFS | BFS ] 미로 탈출

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

:: 입력 조건

 

첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

 

:: 출력 조건

 

첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

 

---

 

  내   코드  

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

#define endl "\n"

int n, m;
int map[201][201] = { 0, };
int dir_x[] = {-1, 1, 0, 0};
int dir_y[] = {0, 0, -1, 1};

int bfs(int x, int y) {

	queue<pair<int, int>> q;
	q.push({ x, y });

	while (!q.empty()) {

		int x = q.front().first;
		int y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int new_x = x + dir_x[i];
			int new_y = y + dir_y[i];
			if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m) {
				continue;
			}
			if (map[new_x][new_y] == 0) {
				continue;
			}
			if (map[new_x][new_y] == 1) {
				map[new_x][new_y] = map[x][y] + 1;
				q.push({ new_x, new_y });
			}
		}
	}

	return map[n - 1][m - 1];
}

int main() {

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf_s("%1d", &map[i][j]);
		}
	}

	int res = bfs(0, 0);

	cout << res << endl;
}

 

  정답  코드  

#include <bits/stdc++.h>

using namespace std;

int n, m;
int graph[201][201];

// 이동할 네 가지 방향 정의 (상, 하, 좌, 우) 
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int bfs(int x, int y) {
    // 큐(Queue) 구현을 위해 queue 라이브러리 사용 
    queue<pair<int, int> > q;
    q.push({x, y});
    // 큐가 빌 때까지 반복하기 
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        // 현재 위치에서 4가지 방향으로의 위치 확인
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 미로 찾기 공간을 벗어난 경우 무시
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            // 벽인 경우 무시
            if (graph[nx][ny] == 0) continue;
            // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if (graph[nx][ny] == 1) {
                graph[nx][ny] = graph[x][y] + 1;
                q.push({nx, ny});
            } 
        } 
    }
    // 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1];
}

int main(void) {
    // N, M을 공백을 기준으로 구분하여 입력 받기
    cin >> n >> m;
    // 2차원 리스트의 맵 정보 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
    // BFS를 수행한 결과 출력
    cout << bfs(0, 0) << '\n';
    return 0;
}

 

  리뷰  

DFS 와 마찬가지로 main에서 사용하는 부분과 bfs 함수 내부의 구현이 잘 떠오르지 않아서 답안 코드를 참고했음

방향벡터를 2차원배열로 선언해서 혼란이 있었고

BFS 알고리즘의 순서를 제대로 이해하지 못해서 BFS 내의 while문을 짜는데 시간이 많이 걸림

 

그리고 최단 경로를 찾을 때 2차원배열 자체에 그 칸까지 가는데에 소모된 칸수를 저장한다는 발상도 떠올리지 못했음