1861 정사각형 방

DP를 사용하지 않아도 풀리는 문제인거 같으나 나는 DP를 활용하여 풀었다.

1. d배열에 각각 위치에서 이동할 수 있는 최대값을 저장한다.

2. 

이동가능할 때 :

d[ax][ay]==0 ? (ax,ay)지점에 한번도 방문하지 않음 -> 방문한다 ( dfs(ax,ay) )

3. d[ax][ay]와 값 비교하여 d[x][y] 를 최대값으로 만든다.

4. 미방문 지점에 대해 반복한다. 

#include <iostream>
#include <algorithm>
using namespace std;
 
int t, n;
int map[1002][1002];
int d[1002][1002];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
void dfs(int x, int y) {
    d[x][y] = 1;
 
    for (int i = 0; i < 4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
 
        if (map[ax][ay] == 0) continue;
 
        if (map[ax][ay] == map[x][y] + 1) {
            if (d[ax][ay] == 0) dfs(ax, ay);
            d[x][y] = max(d[x][y], d[ax][ay] + 1);
        }
    }
}
 
void get_result(int tc) {
    int cnt = 0;
    int num = 987654321;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (cnt < d[i][j]) {
                cnt = d[i][j];
                num = map[i][j];
            }
            else if (cnt == d[i][j]) {
                num = min(num, map[i][j]);
            }
        }
    }
 
    cout << "#" << tc << " " << num << " " << cnt << "\n";
}
 
void printAll() {
    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << d[i][j] << " ";
        }
        cout << endl;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> map[i][j];
                d[i][j] = 0;
            }
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][j] == 0) dfs(i, j);
            }
        }
        get_result(tc);
 
        //printAll();
    }
    return 0;
}