[BFS] 백준 2178번 미로 탐색(C++)

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

 

 

[DFS,BFS] 백준 1260번 BFS와 DFS(C++)

[DFS,BFS] 백준 1260번 BFS와 DFS(C++)

bfs로 풀어야 되는 문제이다

 

지나야 하는 최소의 칸 수를 입력하라 했고,

그걸 bfs로 찾아가는 문제~

dfs로 하면 가장 깊은 방법으로 가기때문에

예를들어

1 1 1

1 1 1

1 1 1

이 있을경우

00 > 01 >02> 12 >11> 10 >20 >21 >>22로 아마 9번을 거쳐야 될 수도 있기에..

 

bfs로 찾아가는 문제이다!

어옷

 

앞서서 다른 bfs를 풀었을때는 이제 1차원 배열로 생각해서 풀었는데 그건 좀 비효율 적인거 같아서 이번엔 pair를 이용한 vector와 queue를 사용할 것이다.

풀이 내용은 대동소이 하지만 우리가 풀던것과는 다르게

 

1.모든 숫자는 붙어있고

2.00에서 n-1 m-1까지의 최소의 수를 구하라

 

이다.

 

모든 숫자는 붙어있으니

단 한번의 bfs만 진행되면 될 것이고

== (0,0)스타트

 

최소의 수를 구하라?

 

나는 여기서 dp를 생각햇다

그 전 것들에서 +1만 해가면 되지 않은가?

 

예를들어

 

 

1	1	1	1
1	0	1	0
0	1	1	1
1	0	0	1
1	1	1	1

 

이런 배열이 있다고 치자

 

그럼 여기서 첫번째에서 마지막인덱스로 가는 방법은?

 

이런 방법일 것이다 

 

그리고 bfs가 숫자를 찾아가는 방식을 생각해보자

첫번째 인덱스에 대해서는 파란색으로 칠한 색깔을 먼저 찾고

 

그 이후는

그 이후는

뭔가 느낌이 오는가?

 

파란색으로 칠한 부분까지의 최소 거리는, 그저 부모 노드 + 1일 뿐인 것이다

 

그래서 자동으로 부모 노드 + 1은 그 거리까지의 최소가 되는 것이다.

 

#include <iostream>

#include <queue>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

bool visited[100][100];

int arr[100][100];

void bfs(int a, int b);

int dp[100][100];

int depth = 0;

vector<pair<int, int>> load;

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

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

int n, m;

int main()

{

    cin >> n >> m;

    dp[0][0] = 1;

    for (int i = 0; i < n; i++)

    {

        string temp;

        cin >> temp;

        for (int j = 0; j < m; j++)

        {

            arr[i][j] = temp[j] - '0';

            // cout << arr[i][j]<<"\n";

            if (arr[i][j])

                load.push_back(make_pair(i, j));

        }

    }

    int a = load[0].first;

    int b = load[0].second;

    bfs(a, b);

    cout << dp[n - 1][m - 1] << "\n";

}

void bfs(int a, int b)

{

    queue<pair<int, int>> q;

    q.push(make_pair(a, b));

    visited[a][b] = true;

    while (!q.empty())

    {

        int x = q.front().first;

        int y = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++)

        {

            // cout << "restart : " << x << " " << y << "\n";

            int nx = x + dx[i];

            int ny = y + dy[i];

            // cout << nx << " " << ny << "\n";

            if (nx >= 0 && ny >= 0 && nx < n && ny < m)

            {

                if (!visited[nx][ny] && arr[nx][ny])

                {

                    dp[nx][ny] = dp[nx - dx[i]][ny - dy[i]] + 1;

                    // cout << nx << " " << ny << " :" << dp[nx][ny] << "\n";

                    visited[nx][ny] = true;

                    q.push(make_pair(nx, ny));

                }

            }

        }

    }

}

자동으로 최소가 되는것을 알면 될 것이다.