잡다한 프로그래밍

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

1. 해결방법

많이 볼 수 있는 DFS 문제로 좌, 우, 아래 순으로 한 번만 체크하는 방식으로 해결하면 금방 풀 수 있을 거라 생각했다.

2. 에러

먼저 100X100 배열을 가로로 입력받아야 하는데 다음과 같은 코드로 세로를 먼저 받게 입력받았다. 이사실을 오랫동안 알아차리지 못해 문제에 오류가 생겼다. 주의하자 array[i][j]가 아닌 [j][i] 여야 한다

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

3. 코드

#include<iostream>

using namespace std;
int array[100][100] = {0};
int chk_array[100][100] = {0};
int result = 0;
int max_value = 9999;
int nx[3] = {-1, 1, 0};
int ny[3] = {0, 0, 1};

void dfs(int x, int y, int start, int count){
    if (y == 99){
        if(count <= max_value){
            max_value = count;
          	result = start;
        }
    }
    else{
        for(int i = 0; i < 3; i ++){
     		int dx = x + nx[i];
        	int dy = y + ny[i];

        	if(dx < 0 || dx >= 100 || dy < 0 || dy >= 100 || chk_array[dx][dy] == 1 || array[dx][dy] == 0 || (y == 0 && i == 0) || (y == 0 && i ==1)) continue;
			else{
                chk_array[dx][dy] = 1;
             	dfs(dx, dy, start, count+1);
                chk_array[dx][dy] = 0;
                break;
            }
    	}
        
    }    
}

int main(int argc, char** argv)
{
   int test_case;
   int T;   
   for(test_case = 1; test_case <= 10; ++test_case)
   {
      cin>>T;
        for(int i = 0; i < 100; i++){
            for(int j = 0; j < 100; j++){
                cin >> array[j][i];
            }
        }
        result = 0; max_value = 9999;
        for(int k = 0; k < 100; k++){
            chk_array[k][0] = 1;
            dfs(k, 0, k, 1);
            chk_array[k][0] = 0;
        }
        cout << "#" << test_case << " " << result << endl;

   }
   return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

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. 해결방법

먼저 전에 가능한 시험 점수라는 문제를 풀면서 가능한 모든 점수를 구하는 문제를 푼 기억이 있어서 같은 방법으로 해결하면 좋겠다 라는 생각을 하였다. 가능한 시험 점수라는 방법으로 문제를 해결했으나, 깔끔한 코드가 아닌 것 같아서 다른 방법이 존재할까 찾아보았고 dfs로 가능하다는걸 알았다. 어렵지 않았는데 왜 dfs로 해결해볼까?라는 생각을 하지 못했다.

2. 코드

#include<iostream>
#include<string.h>
using namespace std;
	int test_case;
	int N;
	int top_height;
	int array[300000];
	int temp = 0;
	int sum = 0;
	int result = 0;
int main(int argc, char** argv)
{
    cin>>test_case;
	for(int i = 1; i <= test_case; i++)
	{
		cin >> N;
        cin >> top_height;
            memset(array, 0, sizeof(array));
        array[0] = 1;
       	for(int j = 0; j < N; j++){
            cin >> temp;
            sum += temp;
            for(int k = sum; k>=0; k--){
             if(array[k] != 0){
                 array[k + temp]++;
             }
            }
        
        }
        
         for(int m = 0; m< 300000; m++){
         if(array[m] !=0 && m >= top_height){
         	result = m - top_height;
                              break;
         }
        }

        
        cout << "#"<<i<<" "<< result << endl;
    }
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

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

1. 해결방법

모든 지점을 상 하 좌 우로 들리면서 7번째로 도착하면 set에 저장하면 자동으로 중복을 제거해 줄 수 있을 거라고 생각했다. 따라서 모든 지점을 상 하 좌 우로 들리는 방법을 코드로 구현하려 하였으나 결국 검색하여 찾아보니 dfs와 bfs방법을 사용한다고 한다. 이 문제의 해결방법으로는 dfs를 사용했고 dfs와 bfs는 따로 나중에 알고리즘에 추가하도록 할 예정이다.

2. 코드

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

int num = 0;
int arr[4][4];
set<int> setary;
void dfs(int x, int y, int val, int dept) {
	int nx[4] = { 0, 0, -1, 1 };
	int ny[4] = { -1, 1, 0, 0 };
	for (int i = 0; i < 4; i++) {
		if (dept == 7) {
			setary.insert(val);
			return;
		}
		int dx = x + nx[i];
		int dy = y + ny[i];

		if (dx < 0 || dx >= 4 || dy < 0 || dy >= 4) continue;
		else {
			dfs(dx, dy, val * 10 + arr[dy][dx], dept + 1);
		}
	}
}
int main()
{
	cin >> num;
	for (int i = 1; i <= num; i++) {
        setary.clear();
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> arr[j][k];
			}
		}
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				dfs(j, k ,arr[j][k], 1);
			}
		}
		cout << "#"<< i << " " << setary.size() << endl;
	}
}

main함수에서 dfs(j, k, arr[j][k], 1)이 부분을 처음에 0, 0 arr[j][k], 1로 하였다 이때 값이 항상 같은 오류가 생겼고 이를 j k로 수정하며 해결하였다.