백준 / 6832 / Maze / C++

간단하게 해석해보면 + 는 상하좌우, - 는 좌우, | 는 상하로 움직일 수 있고, *은 벽인 미로에서 왼쪽 위에서 아래쪽 밑까지의 최단 경로값을 찾는 문제이다.

#include <bits/stdc++.h>

using namespace std;

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

int n, m;

void bfs(vector<vector<char>> &arr, vector<vector<int>> &count)
{
    queue<pair<int, int>> Q;
    Q.push({0, 0});
    count[0][0] = 1;
    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();
        Q.pop();
        if (arr[cur.first][cur.second] == '-')
        {
            for (int i = 0; i < 2; i++)
            {
                int nx = cur.first + dx[i];
                int ny = cur.second + dy[i];
                if (nx >= n || ny >= m || nx < 0 || ny < 0)
                {
                    continue;
                }
                if (arr[nx][ny] == '*')
                {
                    continue;
                }
                if (count[nx][ny] && count[nx][ny] <= count[cur.first][cur.second] + 1)
                {
                    continue;
                }
                count[nx][ny] = count[cur.first][cur.second] + 1;
                Q.push({nx, ny});
            }
        }
        else if (arr[cur.first][cur.second] == '|')
        {
            for (int i = 2; i < 4; i++)
            {
                int nx = cur.first + dx[i];
                int ny = cur.second + dy[i];
                if (nx >= n || ny >= m || nx < 0 || ny < 0)
                {
                    continue;
                }
                if (arr[nx][ny] == '*')
                {
                    continue;
                }
                if (count[nx][ny] && count[nx][ny] <= count[cur.first][cur.second] + 1)
                {
                    continue;
                }
                count[nx][ny] = count[cur.first][cur.second] + 1;
                Q.push({nx, ny});
            }
        }
        else if (arr[cur.first][cur.second] == '+')
        {
            for (int i = 0; i < 4; i++)
            {
                int nx = cur.first + dx[i];
                int ny = cur.second + dy[i];
                if (nx >= n || ny >= m || nx < 0 || ny < 0)
                {
                    continue;
                }
                if (arr[nx][ny] == '*')
                {
                    continue;
                }
                if (count[nx][ny] && count[nx][ny] <= count[cur.first][cur.second] + 1)
                {
                    continue;
                }
                count[nx][ny] = count[cur.first][cur.second] + 1;
                Q.push({nx, ny});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        vector<vector<char>> arr(n, vector<char>(m));
        vector<vector<int>> count(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++)
        {
            string tmp;
            cin >> tmp;
            for (int j = 0; j < m; j++)
            {
                arr[i][j] = tmp[j];
            }
        }
        bfs(arr, count);
        if (count[n - 1][m - 1] == 0)
        {
            cout << -1 << "\n";
        }
        else
        {
            cout << count[n - 1][m - 1] << "\n";
        }
    }
    return 0;
}

dx dy 배열을 선언한 후 -에서는 0~1, |에서는 2~3, +에서는 0~3 인덱스의 dx dy 값을 써서 bfs를 돌렸다. 발상이 어려운 문제는 아닌듯