백준2178번-미로BFS

이 문제는 가중치가 같은 맵 안에서의 최단 경로를 찾는 문제이다. 이는 자료구조 queue를 사용하며 풀면 되는데 나의 코드는 다음과 같다.

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
	int n, m, y,x;
	int max = 104;
    int a[104][104];
    int visited[104][104]; // 입력 배열과 방문 배열 
    int dy[4] = {-1,0,1,0};
    int dx[4] = {0,1,0,-1};
int main() {
	cin >> n;
	cin >> m;
    for(int i = 0; i < n; i++){
        for(int j= 0; j < m;j++)
        {
            cin >>a[i][j];
        }
    }//입력 만들기 

    queue<pair<int,int> > q; // q설정
    visited[0][0] = 1;// 방문 정보를 넣는다. 
    q.push({0,0});
    while(q.size()) // q의 사이즈만큼 반복
    {
        tie(y,x) = q.front(); q.pop();
        for(int i =0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny > n || nx < 0 || nx > m || a[ny][nx] == 0) continue; // 경계조건과 0일 경우
            if(visited[ny][nx]) continue;// 방문을 이미 한 경우
            visited[ny][nx]  = visited[y][x] + 1;
            q.push({ny, nx});

        }
    }
    cout << visited[n-1][m-1] << endl;
    return 0;
}

자 코드를 살펴보겠다. 

우선 우리에게 필요한 정보는 원본의 맵을 담당할 배열, 방문을 체크할 다른 배열, 맵의 크기를 결정할 변수 두 개, 인덱스를 나타낼 변수 두 개, 또한 인접한 영역만 움직일 수 있다고 했으니 index 배열 두 개가 필요하다. 

 

이 문제는 일반적인 BFS문제로써 맵의 입력을 받아준 후 queue 자료형을 생성하고 방문 배열의 시작점을 1로 만들어준다. 

그 후 queue에 시작점을 넣어주면 queue는 FIFO(First In First Out)구조이기 때문에 넣어준 시작점부터 탐색을 하기 시작한다. 그 후 tie함수 (tuple.h안에 존재한다.)를 사용하여 queue의 front를 정의해준 후 pop을 해준다. 그 후 index배열을 통해 x와 y의 새로운 좌표를 구해준 후 그 좌표에 해당하는 방문 배열이 0인지 1인지를 판단한다. 

만약 방문 배열이 0이라면 아직 방문하지 않은 것이니 +1을 해줘 최단 경로의 수로 만들어주고 방금 +|1로 해줬던 배열 인덱스를 다시 queue에 푸쉬해준다. 

 

이 과정에서 boundary처리 같은 경우는 if문 안에서 처리를 해준다. 

 

전형적인 BFS알고리즘으로 요약하면 다음과 같다. 

queue생성

while(q.size()) {}

tie(y,x) = q.front() q.pop()

for(int i=0; i< 4; i++){바운더리 처리 및 조건 처리}

인덱스 배열 계산 

방문 배열 + 1

방금 +1해준 배열 인덱스 다시 queue에 푸쉬