[BFS]2178번 미로탐색

URL : https://www.acmicpc.net/problem/2178

※이 문제 어떻게 풀지?※

BFS와 Queue를 이용하여 최소 이동횟수를 구하고자 했습니다.

※필요 역량 정리하기!!!※

1. pair, make_pair 함수를 사용할 때 => #include<utility>를 사용해 주자!!

 - 백준에서는 C++ 컴파일 에러가 나기 때문... 시험장가서도 똑같겠죠...

2. 결국 BFS...!!  밑에 소스는 <BFS + Queue>

/*
bfs에 대해서 잘 알아야 할 수 있다.

bfs 큐이고 루트에서 인접한 순으로 돌아가며 탐색한다.
*/
 
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
int number = 9;
int visit[9];
vector<int> a[10];
 
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visit[start] = 1;
 
    while (!q.empty()) {
        //큐에 값이 있을 경우 계속 반복 실행
        //큐에 값이 있다. => 아직 방문하지 않은 노드가 존재 한다.
 
        int x = q.front();
        q.pop();
        cout << x << endl;
        for (int i = 0; i < a[x].size(); i++) {
            int y = a[x][i];
            if (!visit[y]) {
                //방문하지 않았다면.
                q.push(y);
                visit[y] = 1;
            }
        }
    }
}
 
int main() {
    a[1].push_back(2);
    a[2].push_back(1);
    
    a[1].push_back(3);
    a[3].push_back(1);
 
    a[2].push_back(4);
    a[4].push_back(2);
 
    a[2].push_back(5);
    a[5].push_back(2);
 
    a[4].push_back(8);
    a[8].push_back(4);
 
    a[5].push_back(9);
    a[9].push_back(5);
 
    a[3].push_back(6);
    a[6].push_back(3);
 
    a[3].push_back(7);
    a[7].push_back(3);
 
    bfs(1);
    return 0;
}

밑에 소스는 미로탐색

/*
미로탐색
*/
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
int n, m;
int a[101][101];
int visit[101][101];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,1,-1 };
 
void bfs(int startx, int starty) {
    queue<pair<int,int> > q;
    q.push(make_pair(startx,starty));
    visit[startx][starty] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (a[nx][ny] == 1 && nx >= 0 && nx < n && ny >= 0 && ny < m) {
                q.push(make_pair(nx,ny));
                a[nx][ny] = a[x][y] + 1;
            }
        }
    }
}
 
int main() {
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    bfs(0, 0);
    cout << a[n - 1][m - 1];
    return 0;
}