[BOJ] 2178 미로 탐색

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

2178번: 미로 탐색

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

bfs

 

---------------------------------------------------풀이----------------------------------------------------

 

(0,0)에서 (N-1,M-1)로 가기 위한 최단 거리를 구하기 위해서는 bfs를 이용한다.

우선, ((x, y), depth)를 저장하는 queue가 필요하며, visited[][] 배열에 방문한 곳은 true로 설정해 다시 방문하지 않도록 한다.

네 방향으로 이동하기 위해 dx[4]와 dy[4] 배열을 준비한다.

처음 시작 점을 ((0,0), 0)으로 설정해 큐에 삽입한다.

큐의 front를 꺼내오며 (N-1,M-1)에 도달했는지 체크하고, 도달했다면 그때의 depth값을 리턴한다.

도달하지 않았다면, dx[i]와 dy[i]를 x,y값에 더해 네 방향을 조사하고, 이동 가능하면서 방문하지 않은 노드라면 depth를 1 증가시켜 큐에 삽입하고 방문한 노드로 설정한다.

 

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int N, M;
int map[101][101] = {0, };
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool visited[101][101] = {false, };

int solution(){
    queue<pair<pair<int,int>, int> > q;
    // 좌표, depth
    pair<pair<int,int>, int> cur;
    cur.first.first = cur.first.second = 0; cur.second = 1;
    q.push(cur);
    visited[0][0]= true;
    while(!q.empty()){
        cur = q.front();
        q.pop();
        if(cur.first.first == N-1 && cur.first.second == M-1){
            return cur.second;
        }
        int nx, ny;
        for(int i = 0; i < 4; i++){
            nx = cur.first.first + dx[i];
            ny = cur.first.second + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == 0
                || visited[nx][ny]){
                continue;
            }
            q.push(make_pair(make_pair(nx, ny), cur.second+1));
            visited[nx][ny] = true;
        }
    }
    return -1;
}

// from (1,1) to (N,M)
int main(void){
    FASTIO;
    cin >> N >> M;
    char tmp;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> tmp;
            map[i][j] = tmp-'0';
        }
    }

    // bfs
    cout << solution() << "\n";

    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------