[SW Expert] #1861. 정사각형 방

https://swexpertacademy.com/main/main.do

SW Expert Academy

1. 해결방법

문제의 상하좌우라는 키워드를 보자마자 완전탐색이 가장 어울릴것이라는 생각이 들었다. DFS를 통해 순차적으로 탐색하면서 카운트 해주는 방법으로 해결하였다

---

2. 코드

#include<iostream>
using namespace std;

int test_case;
int T;
int N;
int ary[1000][1000];
bool ary_check[1000][1000];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int cnt_max = 1;
int val_min = 9999;
void check(int x, int y, int cnt, int start_value){
	ary_check[x][y] = true;
    
    for(int i = 0; i < 4; i++){
  		int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 0 || ny < 0 || nx >= N || ny >= N || abs(ary[nx][ny] - ary[x][y]) != 1 || ary_check[nx][ny]){
         
            
            continue;   
        }
        check(nx, ny, cnt+1, start_value);
      	ary_check[nx][ny] = false;
    }
   
    if(cnt_max < cnt){
             	cnt_max = cnt;
        val_min = start_value;
    }else if(cnt_max == cnt){
     	if(val_min > start_value)
            val_min = start_value;
    }
}

int main(int argc, char** argv)
{
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
                        memset(ary, 0, sizeof(ary));
		for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                cin >> ary[i][j];
            }
        }
        
                        cnt_max = 1;
				val_min = 9999;
        for(int k = 0; k < N; k++){
            for(int n = 0; n < N; n++){

                check(k, n, 1, ary[k][n]);
                ary_check[k][n] = false;
            }
        }
        
		cout << "#" << test_case << " " << val_min << " " << cnt_max << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}