[백준] 2178 미로 탐색 bfs

문제 : 

www.acmicpc.net/problem/2178

2178번: 미로 탐색

분석 :

이 문제는 경로 탐색 문제이다. DFS, BFS 둘 중 아무거나 풀어도 상관 없어 보인다. 나는 BFS 연습을 위해 BFS 방식으로 풀었다. cin 은 공백 기준으로 input을 받는 것 같아서 scanf의 도움을 받았다. cin 으로 풀 수있는 방법 알면 알려주시면 감사하겠습니다. 🥺 

2차원 행렬에 값이 1 (지나갈 수있는 칸) 인경우 true로 담았고 아니면 false로 값을 초기화 하였다. 

이 문제는 input 값이 0,0 일때 모두 1이어서 start를 0,0 으로 고정시켜 했는데 다른 문제 풀때에는 0,0이 1인지 확인 한 뒤에 갈 수 있는 길을 찾으면 그때 start값으로 넣어줘야겠다

먼저 queue에 찾은 좌표값을 넣어주고 up down left right를 돌면서 1이 있다면 그리고 visit한 장소가 아니라면 다시 q에 push 하며 경로를 탐색한다. visit에 값을 누적시킨 뒤 그 값을 인자로 전달했다. 이상하게 cnt 변수로 값을 증가시키면 안된다.. 뭘까 하나씩 적게 나온다 

 

c++ 코드 :

//
//  2178_miro.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/13.
//

#include <stdio.h>
#include <cstdio>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
#define MAX 100

int visit[MAX][MAX];
bool map[MAX][MAX];

int N, M;
int dx[] = { 0, 0, 1, -1 }; //up down left right
int dy[] = { 1, -1, 0, 0 };

int miro_bfs(pair<int, int> start){
    //memset(visit, false, sizeof(visit));
    visit[start.second][start.first] = true;

    queue<pair<int,int>>q;
    q.push(make_pair(start.second, start.first));
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        //cout << y << " " << x << endl;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= 0 && ny >= 0 && ny < N && nx < M){
                if(visit[ny][nx] == false && map[ny][nx]){ // 방문 x 이고 갈 수 있는 길이면
                    visit[ny][nx] = visit[y][x] + 1;
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
    return visit[N-1][M-1];
}


int main(){
    cin >> N >> M;
    //cout << N << M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            int a;
            scanf("%1d", &a);

            if(a == 1){
                map[i][j] = true;
            }else{
                map[i][j] = false;
            }
        }
    }
//input 확인
//    for(int i = 0; i < N; i++){
//        for(int j = 0; j < M; j++){
//            cout << map[i][j] << " " ;
//        }
//        cout << endl;
//    }


    pair<int, int> start = make_pair(0, 0);

    cout << miro_bfs(start) << endl;

    return 0;
}