백준 2178 - 미로 탐색(C++)

문제 링크입니다 https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

BFS 문제였습니다

문제 조건

출력 예시

 

 

문제 접근 방법

1. 미로를 입력 받는다.

2. (1,1) 부터 (N,M) 까지 BFS를 통해서 최소 거리를 탐색한다.

 

 

문제 접근 방법 - 2번

void bfs(int a, int b){
    q.push({a,b});
    while(!q.empty()){
        int x1 = q.front().x;
        int y1 = q.front().y;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x1 + arr[i];
            int yy = y1 + arr2[i];
            if(xx >= 1 && yy >= 1 && xx <= num && yy <= num2){
                if(check[xx][yy] == 0 && miro[xx][yy] == '1'){
                    check[xx][yy] = check[x1][y1] + 1;
                    q.push({xx,yy});
                }
            }
        }
    }
}

4방향 탐색을 통해서 좌표 범위에 맞으면서, 이전에 방문하지 않았으며, 길이 존재할 경우, 큐에 넣어주면서 탐색을 이어줍니다.

check[] 배열에 이동한 횟수를 저장했습니다!!

 

 

 

자세한 것은 코드를 참고해주세요!

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cstring>
#include <cmath>
using namespace std;

int num, num2;
char miro[101][101];
int check[101][101];
typedef struct qu{
    int x;
    int y;
}qu;
queue<qu> q;
int arr[4] = {1,-1,0,0};
int arr2[4] = {0,0,1,-1};

void bfs(int a, int b){
    q.push({a,b});
    while(!q.empty()){
        int x1 = q.front().x;
        int y1 = q.front().y;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x1 + arr[i];
            int yy = y1 + arr2[i];
            if(xx >= 1 && yy >= 1 && xx <= num && yy <= num2){
                if(check[xx][yy] == 0 && miro[xx][yy] == '1'){
                    check[xx][yy] = check[x1][y1] + 1;
                    q.push({xx,yy});
                }
            }
        }
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> num >> num2;
    for(int i = 1; i<= num; i++){
        for(int j = 1; j <= num2; j++){
            cin >> miro[i][j];
        }
    }
    for(int i = 1; i <= num; i++){
        for(int j = 1; j <= num2; j++){
            if(check[i][j] == 0 && miro[i][j] == '1'){
                check[i][j] = 1;
                bfs(i,j);
            }
        }
    }
    cout << check[num][num2];
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!