백준 2178번 미로 탐색[C++]

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

2178번: 미로 탐색

 

#문제 간단 정리

핵심: 최단거리 문제는 BFS 를 사용하자

DFS를 사용하면 시간 초과가 난다

쉽게 생각해보면 하나의 길을 끝까지 갔다가

다시 되돌아 와서 다시 가니까 

BFS보다 시간이 훨씬 더 걸릴 거라는 것을 알아낼 수 있다.

#문제 해결 방법

1. 전역 변수 선언:
   • maze[100][100]: 미로 정보 저장 (1은 이동 가능, 0은 이동 불가능).
   • check[100][100]: 해당 위치를 방문했는지 여부를 저장.
   • dist[100][100]: 시작점부터 해당 위치까지의 이동 횟수를 저장.
   • dx[], dy[]: 주변 4 방향(상, 하, 좌, 우)을 탐색하기 위한 좌표 변경값.
   • q: BFS(너비 우선 탐색)에 사용되는 큐.
2. findWay 함수:
   • BFS를 사용하여 미로 탐색.
   • 현재 위치에서 상하좌우 4 방향을 탐색하여 이동 가능하고 아직 방문하지 않은 위치를 큐에 추가.
   • 큐에서 뽑힌 위치는 이미 방문한 것이므로 check를 true로 설정.
   • 이동 횟수(dist)는 이전 위치의 이동 횟수 + 1.
3. main 함수:
   • 입력을 받아 미로를 초기화.
   • 시작점인 (0, 0)을 큐에 추가하고 check와 dist를 초기화.
   • findWay 함수를 호출하여 BFS로 미로 탐색.
   • 최종 목적지인 (n-1, m-1)까지의 최단 이동 횟수를 출력.

이 코드의 핵심은 BFS를 사용하여 미로 내에서의 최단 경로를 찾는 것입니다. BFS는 모든 가능한 경로를 너비 우선으로 탐색하므로 최초로 목적지에 도달할 때, 그 경로는 가장 짧은 경로가 보장됩니다.

#전체 코드

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

using namespace std;

int n, m;

int maze[100][100];
int check[100][100] = { false };
int dist[100][100];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1,-1,0,0 };
queue<pair <int, int>> q;

void findWay(queue<pair<int,int>> q) {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (check[nx][ny] == false && maze[nx][ny] == 1) {
                    q.push(make_pair(nx, ny));
                    dist[nx][ny] = dist[x][y] + 1;
                    check[nx][ny] = true;
                }
            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        string input; cin >> input;
        for (int j = 0; j < m; j++) {
            if (input[j] == '1') {
                maze[i][j] = 1;
            }
            else {
                maze[i][j] = 0;
            }
        }
    }

    q.push(make_pair(0, 0));
    check[0][0] = true;
    dist[0][0] = 1;

    findWay(q);

    

    cout << dist[n-1][m-1];

    return 0;
}