[1일 1알고] 23352 방탈출

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

---

개요

1번 조건에 의해 bfs계열 탐색을 해야함을 알 수 있습니다.

각 격자 당 추가적인 가중치가 존재하지 않기 때문에 굳이 다익스트라 등의 알고리즘을 사용할 필요는 없고 bfs를 사용할 것입니다.

 

전체에서 가장 긴 거리를 찾아야 하는데, 딱히 추가적인 조건이 없기 때문에 하나하나 bfs를 해야되나 싶습니다.

그런데 문제에서 조건이 N,M <= 50이기 때문에 최악의 경우에도 1초를 넘기기는 쉽지 않아보여 모두 탐색하기로 했습니다.

---

코드

using namespace std;

int N, M;
void bfs(int sr, int sc, vector<vector<int>>& v, int* pmax_dist, int* presult);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // NxM크기, 각 칸에는 0~9 값이 주어짐
    // 상하좌우로 움직이며 0값은 장애물
    // 비밀번호는 
    // 1.방->방 최단 경로, 
    // 2.1번을 만족하는 경로 중 가장 긴 경로의 시작 방과 끝방에 적힌 숫자의 합


    cin >> N >> M;

    vector<vector<int>> v(N, vector<int>(M, 0));
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> v[i][j];
        }
    }
    
    int result = 0;
    int max_dist = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (v[i][j] != 0)
            {
                bfs(i, j, v, &max_dist, &result);
            }
        }
    }

    cout << result;

    return 0;
}

int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

struct room
{
    int r, c, dist;
};

void bfs(int sr, int sc, vector<vector<int>>& v, int* pmax_dist, int* presult)
{
    vector<vector<bool>> visited(N, vector<bool>(M, false));

    queue<room> q;
    q.push({ sr, sc, 0 });
    visited[sr][sc] = true;

    if (*pmax_dist == 0)
    {
        *presult = max(*presult, v[sr][sc]*2);
    }

    while (!q.empty())
    {
        auto[r, c, dist] = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < N && nc >= 0 && nc < M && !visited[nr][nc] && v[nr][nc]!=0)
            {
                q.push({ nr, nc, dist + 1 });
                visited[nr][nc] = true;
                if (dist + 1 > *pmax_dist)
                {
                    *pmax_dist = dist + 1;
                    *presult = v[nr][nc] + v[sr][sc];
                }
                else if (dist + 1 == *pmax_dist)
                {
                    *presult = max(*presult, v[nr][nc] + v[sr][sc]);
                }

            }
        }
    }
}

 

최장거리에 대한 거리만 신경써준다면 쉽게 풀 수 있는 문제입니다.