[c++][BFS] 백준 2178번 문제 풀이

BFS 문제 중 기본 문제이다.

BFS , DFS 문제를 찾고 있다면 이 문제를 풀어보는 것을 추천한다.

 

 

풀이

 

◎ BFS 방식으로 해결 한다. (queue STL을 사용한다.)

◎ 한번 움직일 때마다 현재 몇번 왔는지를 기록한다. (map에 기록해 두었다.)

◎ 경계를 넘지 않고 , 1이면 이동한다.

 

BFS 방식으로 상하좌우 모두 이동 가능한지 확인 해보고 가능 하다면 queue에 저장.

queue에 담긴 좌표를 하나씩 꺼내보면서 탐색. queue에서 모두 꺼내고, 비게 되었다면 탐색을 마친다.

반드시 도착 경로가 있기 때문에 , 탐색을 마쳤을 때 이동 횟수가 map[N][M]에 저장 되어 있다.

 

 

Coding

 

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

using namespace std;

int map[101][101];
queue<pair<int,int>> q;
int x , y;
int nx ,ny;
int move_one[4][2] = { {0,1} , {0,-1} , {1,0} , {-1,0} };
int N , M;

void BFS(){
    pair<int,int> p = {1,1};
    q.push(p);

    while(!q.empty()){
        x = q.front().second;
        y = q.front().first;
        q.pop();

        for(int i = 0 ; i < 4 ; ++i){

            nx = x + move_one[i][0];
            ny = y + move_one[i][1];
            
            if(nx >=1 && nx <= M && ny >= 1 && ny <= N && map[ny][nx] == 1){
                q.push({ny,nx});
                map[ny][nx] = map[y][x] + 1;
            }
        }
    }

    
}

int main(int args ,char** argv){
    cin >> N >> M;

    string temp;
    for(int i = 1 ; i <= N ; ++i){
        cin >> temp;
        for(int j = 1 ; j <= temp.size() ; ++j){
            map[i][j] = temp[j-1]-'0';   
        }   
    }
    BFS();

    cout << map[N][M];
}

 

백준 2178번 문제

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

로그인