[백준/c++] 2178번: 미로 탐색

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

2178번: 미로 탐색

 

문제 요약

 

N x M크기의 미로

1 : 이동할 수 있는 칸  0 : 이동할 수 없는 칸

(1, 1)에서 출발해 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하라

서로 인접한 칸으로만 이동 가능

(칸을 셀 때, 시작 위치와 도착 위치도 포함)

 

 

범위

 

N, M(2 ≤ N, M ≤ 100)

각각의 수들은 붙어서 입력으로 주어진다.

 

 

 

---

 

이동 가능한 방향은 인접칸으로만 가능하므로 상하좌우

dis 배열을 통해 이동횟수를 더하고 초기값을 0으로 해서 만약 0이 아니라면 방문한 것으로도 체크할 수 있도록 했다.

입력된 값이 붙어서 주어졌기 때문에 문자열로 받아서 정수형으로 변경해 miro 배열에 넣어줬다. 

(이 부분은 그냥 char[][] 2차원 배열로 받아도 된다. 뒤늦게 알아차린..)

 

 

BFS를 통해 최소 이동 횟수를 구할 수 있다. 이동한 좌표가

 

- 범위 밖

- 이동불가한 곳 (0)

- 방문한 곳

 

를 제외한 곳이라면 이동할 수 있다.

 

#include <iostream>
#include <queue>
using namespace std;
int n, m, miro[101][101];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int dis[101][101];
string s;

void input(){
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> s;
        for(int j=0; j<m; j++) miro[i+1][j+1] = s[j] - '0';
    }
}

void BFS(){
    queue<pair<int, int>> q;
    q.push({1, 1}); //출발 위치
    dis[1][1] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(dx < 1 || dy < 1 || dx > n || dy > m) continue; //범위 밖 - 패스
            if(miro[dx][dy] == 0) continue; //이동불가한 곳 - 패스
            if(dis[dx][dy] != 0) continue; //방문한 곳 - 패스
            dis[dx][dy] = dis[x][y] + 1;
            q.push({dx, dy});
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    BFS();
    cout << dis[n][m] << '\n';
    return 0;
}

 

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!