백준 1937번: 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

 

키워드 - DFS, 구현

 

Source

 

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
#include <cstring>

using namespace std;

#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
#define ll long long

int sol = 0;
int n;
int table[501][501];
int visited[501][501];

int cx[4] = { 0,  0,  -1, +1};
int cy[4] = {+1, -1,  0 ,  0};
// 상 하좌우 

void dfs(int x, int y, int data) {

    int value = 0;
    for(int i=0; i<4; i++) {

        int dx = x + cx[i];
        int dy = y + cy[i];

        if (dx < 0 || dy < 0 || dx > n || dy > n) {
            // 이동할 위치가 좌표 보다 크거나 음수인경우 움직이지 않도록 한다.
            continue;
        }

        if(table[x][y] < table[dx][dy]) {
            if(visited[dx][dy] == 0)
                dfs(dx, dy, table[dx][dy]);

            if (value < visited[dx][dy]) 
                value = visited[dx][dy];
        }
    }

    visited[x][y] = value +=1;

    if (sol < visited[x][y])
        sol = visited[x][y];
}
int main() {

    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n; 

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> table[i][j];
        }
    }

    for(int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if(!visited[i][j]) {
                dfs(i, j,0);
            }
        }
    }

    cout << sol << CENDL;
    return 0;
}