맛있는감귤

BOJ : 2178 미로찾기 본문

알고리즘/백준 알고리즘

BOJ : 2178 미로찾기

맛있는감귤 2017. 1. 19. 13:21

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

github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2178.cpp

지극히 기본적인 BFS 문제


#include <iostream>
#include <queue>
using namespace std;

int N,M,ans=1;
queue<pair<int, int>> q;
char map[102][102];
bool isVisited[102][102];
int px[4]={1,-1,0,0};
int py[4]={0,0,1,-1};

int main(){
    cin>>N>>M;
    for(int i=0; i<N; i++)
        cin>>map[i];
    
    pair<int, int> s;
    s.first=0, s.second=0;
    isVisited[s.first][s.second]=true;
    q.push(s);
    while(!q.empty()){
        
        int q_size = q.size();
        while(q_size--){
            
            pair<int, int> p;
            p=q.front(); q.pop();
            int x=p.first, y=p.second;
            if(x==N-1 && y==M-1){
                cout<<ans<<'\n';
                return 0;
            }
            for(int i=0; i<4; i++){
                if(x+px[i]>=0 && x+px[i]<N && y+py[i]>=0 && y+py[i]<M && !isVisited[x+px[i]][y+py[i]] && map[x+px[i]][y+py[i]]=='1'){
                    
                    pair<int, int> temp;
                    temp.first = x+px[i]; temp.second = y+py[i];
                    q.push(temp);
                    isVisited[x+px[i]][y+py[i]]=true;;
                }
            }
        }
        ans++;   
    }
}

'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

BOJ : 2292 벌집  (0) 2017.01.19
BOJ : 2206 벽 부수고 이동하기  (2) 2017.01.19
BOJ : 1966 프린터 큐  (2) 2017.01.19
BOJ : 1965 상자넣기  (0) 2017.01.19
BOJ : 1932 숫자삼각형  (0) 2017.01.19