다시 풀어보기**백준 2178번 미로 탐색(C++)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

1. 처음에는 입력받는 것부터 헤맸다.

붙어있는 숫자에서 하나씩 입력받는 건 "%1d" 를 쓰면된다.

 

2. 좌표 문제가 나오면 struct를 써주면 편할 것 같다.

 

3. bfs는 queue와 노드 방문 여부를 사용한다는 것.

 

4. 방문 여부를 for문 안에 넣었을 때는 메모리초과가 떴는데 밖으로 빼니까 통과했다.

 

#include <iostream>
#include <queue>

using namespace std;

struct Edge{
    int x, y,cost;
    
    Edge(int _x, int _y, int _cost){
        x = _x;
        y = _y;
        cost=_cost;
    }
};

int n,m;
int map[101][101] = {0,};
int isVisited[101][101]={false,};
queue<Edge> que;

int posX[4]={-1,0,1,0};
int posY[4]={0,1,0,-1};

bool isInside(int x, int y){
    return (x>=1)&&(x<=n)&&(y>=1)&&(y<=m);
}

int bfs(int x, int y){
    que.push(Edge(x,y,map[x][y]));
    
    while(!que.empty()){
        Edge cur = que.front();
        que.pop();
        
        if(isVisited[cur.x][cur.y]){continue;}
        isVisited[cur.x][cur.y]=true;
        
        if(cur.x==n && cur.y==m) return cur.cost;
        
        for(int i=0;i<4;i++){
            int nextX=cur.x+posX[i];
            int nextY=cur.y+posY[i];
            
            if(isInside(nextX, nextY)==false){continue;}
            if(map[nextX][nextY]==0){continue;}
            que.push(Edge(nextX, nextY,cur.cost+1));
        }
        
    }
    return 0;
}

int main(){
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    cout<<bfs(1,1);
   
    
    return 0;
}

<참고>

sweetday-alice.tistory.com/177

[C++][백준 2178] 미로탐색 - BFS를 이용한 최단거리

위 블로그가 도움이 많이 되었다.

 

BFS는 인접한 노드를 먼저 탐색하는 방법이고, 두 노드 사이의 최단경로나 임의의 경로를 찾을 때 사용된다.

queue와 노드 방문 여부를 이용

 

blog.naver.com/sr5757/222050822368

BFS / 미로탐색 (백준 2178) / C++ ⭐

여기에는 모르는게 좀 나오는데 나중에 다시 보면 좋을 것 같다.