잡다한 프로그래밍

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

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을 리턴해야합니다.
}

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

1. 해결방법

1-1 오류발생

먼저 한 사람씩 비교하여 방문지로 체크했다가 다음 사람은 전에 방문했던적이 있는지 없는지 비교하여 cnt를 ++ 해주는 방법을 사용하였으나 첫방문자가 1~400까지 방문했을경우 나머지는 모두 ++ 되어버리는 오류가 존재하였다

1-2 오류코드

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

int N;
int now_room;
int next_room;
int cnt = 0;
int room[401] = {0};
int now_check;
int next_check;

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        memset(room, 0 , sizeof(room));
        cnt = 1;
        cin>>N;
        for(int i = 0; i < N; i++){
            cin >> now_room;
            cin >> next_room;
            if(now_room > next_room){
                swap(now_room, next_room);
            }
            
            for(int k = now_room; k<=next_room; k++){
                if(room[k]){
                     cnt++;
                    break;
                }
            }
            
                for(int j = now_room; j <= next_room; j++){
                    room[j] = 1;
                }
            
        }
        cout << "#" << test_case << " " << cnt << endl;
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

2. 해결

1번 방법과 비슷한대신 방문지를 ++해주고 마지막에 방문지중 가장 큰 값을 return한다 이방법으로 1번의 오류를 해결하였다

코드

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

int N;
int now_room;
int next_room;
int room[401] = {0};
int now_check;
int next_check;
int cnt = 0;
int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		memset(room, 0 , sizeof(room));
        cin>>N;
        for(int i = 0; i < N; i++){
            cin >> now_room;
            cin >> next_room;
            if(now_room > next_room){
				swap(now_room, next_room);
            }

            if((now_room % 2) == 0) now_room--;
            if((next_room % 2) == 1) next_room++;
            
            for(int j = now_room; j <= next_room; j++){
             room[j]++;   
            }
        }
        cnt = *max_element(room, room+401);
        cout << "#" << test_case << " " << cnt << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}