[백준 C++] 23352 방탈출

문제

여러 방들로 둘러싸인 구역을 탈출해야 한다. 알맞은 비밀번호를 입력하면 탈출할 수 있다.

구역의 지도는 $N \times M$ 크기의 격자판으로 나타낼 수 있으며 각 칸은 방을 의미하고 각 칸에는 0부터 9까지의 숫자가 적혀있는데 이는 해당하는 방에 적힌 숫자를 의미한다.

상하좌우 4가지 방향으로만 움직일 수 있으며, 0이 적힌 방은 들어갈 수 없다.

비밀번호의 힌트는 다음과 같다.

임의의 방에서 다른 방으로 이동할 때는 항상 두 방 사이의 최단 경로로 이동한다.
1번을 만족하는 경로 중 가장 긴 경로의 시작 방과 끝 방에 적힌 숫자의 합
만약 위 2가지 조건을 만족하는 경로가 여러 개라면, 시작 방과 끝 방에 적힌 숫자의 합이 가장 큰 값이 비밀번호가 된다.

시작 방과 끝 방은 동일한 위치일 수도 있다.

<예시> $5 \times 5$ 형태의 지도가 주어질 때, 위의 2가지 조건을 만족하는 경로는 다음과 같다.

이 때 비밀번호가 무엇인지를 구해라.

만약 비밀번호를 만들 수 없는 경우 0을 출력한다.

입력

첫줄에 지도의 세로 크기 $N$($1 \le N \le 50$), 가로 크기 $M$($1 \le M \le 50$)이 공백을 두고 주어진다.

둘째 줄부터 $N$줄에 걸쳐 각 방들의 정보 $A$($0 \le A \le 9$)가 공백을 두고 주어진다.

출력

올바른 비밀번호를 출력한다.

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

풀이

가장 먼저 이문제에서 DFS를 사용할지 BFS를 사용할지 판단해봐야한다.
1. 가중치 없는 2차원 지도
2. 가장 긴 경로중 하나
위 둘에 적합한 탐색법은 BFS이다. 가장 긴 경로를 구할려면 BFS가 필요.

이제 문제에서 구현해야할점은 두가지이다.
1. 가장 긴 경로의 길이
2. 해당 경로에서 시작방, 끝방의 합
경로의 길이를 BFS에서 나타내기위해서 두가지 방법을 생각할 수 있다.
큐에넣을때 길이정보를 넣던가 그전에 함수내에서 구현하던가.
필자는 후자를 선택하여 구현했다.
여기서 보통 BFS코드는 while(!pass.empty()){ ''' }로 끝날텐데
경로의 크기를 재야하므로
while문하나를 더 추가해 이중 while문을 사용했다.
매번 4방향으로의 움직임을 정할때마다 각 방향의 한칸앞의 칸의 숫자를 현재 칸의 숫자와비교해서 최댓값 max를 구하고,
만약 끝방이면 이 부분에서 끝나므로
그대로 경로길이, max, 시작방숫자들을 잘 리턴하면된다.

아래는 BFS함수를 사용하는 부분이다.

매우 간단하게 모든칸에서 BFS를 진행하도록 하는것이다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define MAX 50
using std::vector; using std::stack; using std::queue;
using std::deque; using std::string; using std::pair;
using std::sort;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef pair<string, string> pss;

int N, M;
int map[MAX][MAX];
bool visited[MAX][MAX];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
void init();
void func();
pii bfs(int start_x, int start_y);
void reset();
void init() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0, temp; j < M; j++) {
            scanf("%d", &temp);
            map[i][j] = temp;
        }
    }
}

void func() {
    pii res = {0, 0};
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < M; y++) {
            if (map[x][y] == 0) continue; //시작위치가 0이면 불가능
            pii values = bfs(x, y);
            if (res.first < values.first) //길이가 더 긴것은 무조건 추가
                res = values;
            else if (res.first == values.first && 
                res.second < values.second) //길이가 같은것이면 숫자합이 큰것으로
                res = values;
        }
    }
    printf("%d", res.second);
}


//x,y에서 출발하는 가장 긴 경로의길이, 숫자합을 구함
pii bfs(int start_x, int start_y) {
    reset();
    queue<pii> pass;
    pass.push({ start_x, start_y });
    visited[start_x][start_y] = true;
    int len = 0;
    int max = 0;
    while (!pass.empty()) {
        len++;
        int size = pass.size();
        while (size--) {
            //현재 길이(len)에서의 숫자 최댓값을 구함
            //반복하다보면 끝방에서의 숫자 최댓값이 max에 담김.
            int x = pass.front().first;
            int y = pass.front().second;
            pass.pop();
            max = map[x][y];
            for (int dir = 0; dir < 4; dir++) {
                int xx = x + dx[dir];
                int yy = y + dy[dir];
                if (xx < 0 || yy < 0 || xx == N || yy == M ||
                    visited[xx][yy] || map[xx][yy] == 0) continue;

                visited[xx][yy] = true;
                if (max < map[xx][yy]) max = map[xx][yy]; //최댓값을 구함
                pass.push({xx, yy});
            }
        }
        
    }
    return { len, map[start_x][start_y] + max };
}

void reset() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            visited[i][j] = false;
}

int main(void) {
    init();
    func();


    return 0;
}