BOJ(백준) 3482 - Labyrinth

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

---

자료구조(트리), 트리의 지름

R x C(3 <= R, C <= 1000)인 격자형 그래프가 주어진다. 그래프는 '#'과 '.'로 구성되어있으며, '.'가 인접하여 주어질 경우 로프로 연결할 수 있다. 임의의 두개 '.'는 항상 경로가 존재하며, 그 경로는 항상 유일하다. 격자형 그래프에서 가장 긴 로프의 길이를 구하시오.

---

시간복잡도 : O(R*C)

---

점검해봐야 할 부분

- 트리임을 알아내면 문제가 쉬워진다.

- 격자형 그래프에서 '트리'임을 알아냈어야 한다. (경로가 항상 존재하며 그 경로는 유일하다.)

- 트리의 지름 증명

- 그래프에서 트리. 트리의 지름? 난이도가 어떨까.

---

https://github.com/jongwuner/Algorithm/blob/master/BOJ/3482.cpp

#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX 1005
using namespace std;
typedef pair<int, int> Pair;
const int mvR[] = { 1, 0, -1, 0 };
const int mvC[] = { 0, -1, 0, 1 };
int row, col, ans;
bool arr[MAX][MAX], visit[MAX][MAX];
Pair diaIdx;
void arrToVisit() {
    for (int i = 1; i <= row; i++)
        for (int j = 1; j <= col; j++)
            visit[i][j] = arr[i][j];
}
 
void dfs(int r, int c, int lev) {
    visit[r][c] = false;
    if (ans < lev) {
        ans = lev;
        diaIdx = { r, c };
    }
    for (int k = 0; k < 4; k++) {
        int nextR = r + mvR[k];
        int nextC = c + mvC[k];
        if (nextR < 1 || nextR > row || nextC < 1 || nextC > col) continue;
        if (visit[nextR][nextC]) {
            dfs(nextR, nextC, lev + 1);
        }
    }
}
 
int main() {
    int testCases;
    scanf("%d", &testCases);
    while (testCases--) {
        diaIdx = { 0, 0 }; ans = 0;
        memset(arr, false, sizeof(arr));
        scanf("%d %d", &col, &row);
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                char tmp;
                scanf(" %c", &tmp);
                if (tmp == '.') {
                    arr[i][j] = true;
                }
            }
        }
        arrToVisit();
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (visit[i][j]) {
                    dfs(i, j, 0);
                }
            }
        }
        arrToVisit();
        dfs(diaIdx.first, diaIdx.second, 0);
        printf("Maximum rope length is %d.\n", ans);
    }
    return 0;
}