[Algorithm]Baekjoon 1261번 :: 알고스팟

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

1261번: 알고스팟

 

struct Node
{
    int y;
    int x;
};
 
int n, m;
int arr[100][100];
int dist[100][100];
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
void BFS()
{
    memset(dist, 0x3f, sizeof(dist));
 
    queue<Node> q;
    q.push({ 0,0 });
    dist[0][0] = 0;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (nextY < 0 || nextY == n) continue;
            if (nextX < 0 || nextX == m) continue;
 
            if (dist[curY][curX] + arr[nextY][nextX] < dist[nextY][nextX])
            {
                dist[nextY][nextX] = dist[curY][curX] + arr[nextY][nextX];
                q.push({ nextY,nextX });
            }
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> m >> n;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
 
        for (int j = 0; j < s.size(); ++j)
        {
            arr[i][j] = s[j] - '0';
        }
    }
 
    BFS();
 
    cout << dist[n - 1][m - 1];
}

내가 어떤 유형에 약한지 알 수 있었던 문제.. 

문제난이도를 객관적으로 봤을땐 사실 빨리 풀었어야했는데 그러지 못했다.

생각해보니 네오플코테 봤을때도 이런 유형이였던거같은데...