[Algorithm]Baekjoon 4485번 :: 녹색 옷 입은 애가 젤다지?

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

4485번: 녹색 옷 입은 애가 젤다지?

struct Node
{
    int y;
    int x;
};
 
int n;
int arr[125][125];
int dist[125][125];
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
vector<int> answers;
 
void BFS()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0][0] = arr[0][0];
 
    queue<Node> q;
    q.push({ 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 == n) continue;
 
            if (dist[curY][curX] + arr[nextY][nextX] < dist[nextY][nextX])
            {
                dist[nextY][nextX] = dist[curY][curX] + arr[nextY][nextX];
                q.push({ nextY,nextX });
            }
        }
    }
 
    answers.push_back({ dist[n - 1][n - 1] });
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    while (1)
    {
        cin >> n;
        if (n == 0) break;
 
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                cin >> arr[i][j];
            }
        }
 
        BFS();
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        printf("Problem %d: %d\n", i+1, answers[i]);
    }
}

바로 이전문제를 풀고 왔어서 그런가, 금방 풀긴 했다.

좀 더 상위호환문제를 풀어봐야겠다.