코딩 테스트 준비! (백준)/BFS

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

lee-soo 2025. 4. 24. 14:58

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

 

 

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

 

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

https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그

lee-soo.tistory.com

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));
                }
            }
        }
    }
}

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