[c++] n*m 격자 무늬, 행렬 BFS 알고리즘 문제 코드

 

n행, m열의 행렬을 받고 상하좌우 4방향으로 한 칸씩 옮기면서 해답을 찾아가는 BFS 문제를 해결하기 위한 응용 코드입니다.

문제에서 주어진 조건을 잘 읽고 아래 코드를 응용해서 풀이하면 됩니다.

 

🗓 코드

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

#define MAXINT 100

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

int n, m, start_y, start_x;
int arr[MAXINT][MAXINT];
bool visited[MAXINT][MAXINT];
queue<pair<int, int>> q;

void bfs()
{
    q.push({start_y, start_x});
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            if (arr[ny][nx] == NEXT_ROUTE && !visited[ny][nx])
            {
                visited[ny][nx] = true;
                q.push({ny, nx});
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == START_POINT)
                start_y = i, start_x = j;
        }

    bfs();
    return 0;
}

 

🗓 백준 문제

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

7576번: 토마토

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

2638번: 치즈

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

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유