잡다한 프로그래밍

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

1. 해결방법

크루스칼 알고리즘과 Union find를 이용하여 해결.

2. 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, K;
vector<pair<int, pair<int, int>>> vec;
int Parent[10001];
int result = 0;

int Find(int x) {
    if (x == Parent[x])
        return x;
    else
        return Parent[x] = Find(Parent[x]);
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if(x!=y) Parent[y] = x;
}

bool SameParent(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return true;
    return false;
}

int main(int c, char** v)
{
    cin >> N >> K;

    for (int i = 0; i < K; i++) {
        int x = 0, y = 0, cost = 0;
        cin >> x >> y >> cost;
        vec.push_back(make_pair(cost,make_pair(x, y)));
    }
    sort(vec.begin(), vec.end());
    for (int i = 1; i <= N; i++) {
        Parent[i] = i;
    }

    for (int i = 0; i < K; i++) {
        if (SameParent(vec[i].second.first, vec[i].second.second) == false) {
            Union(vec[i].second.first, vec[i].second.second);
            result += vec[i].first;
        }
    }
    cout << result;
}

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

1. 해결방법

열 단위로 램프가 켜지기 때문에 같은 패턴을 띄어야만 행의 램프가 켜질 수 있다 따라서 1행이 0 1 이라면 나머지 2 3행에서 0 1 패턴이 있는지 찾고 이를 반복적으로 수행하면 된다. 또한 0의 개수가 K보다작은지, K%2 = 0%2인지 비교해주면 된다

2. 코드

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

int N, M, K;
string ary[51];
int max_value = 0;

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> ary[i];
	}
	cin >> K;
	
		for (int j = 0; j < N; j++) {
			int zero_cnt = 0;
			for (int k = 0; k < M; k++) {
				if (ary[j][k] == '0') {
					zero_cnt++;
				}
			}
			int cnt = 0;
			if (zero_cnt <= K && zero_cnt % 2 == K % 2) {
				for (int m = 0; m < N; m++) {
					if (ary[j] == ary[m]) {
						cnt++;
					}
				}
			}
			max_value = max(max_value, cnt);
		}
		cout << max_value;
}

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

1. 해결방법

N, M의 최대수가 적으므로 DFS를 통해 해결하였다.

2. 코드

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

int test_case;
int M,N,K;
int ary[51][51];
int chk[51][51];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int result = 0;

void dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= M || ny < 0 || ny >= N || chk[nx][ny] || ary[nx][ny] == 0) continue;
		else {
			chk[nx][ny] = 1;
			dfs(nx, ny);
		}
	}
}

int main()
{
	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		cin >> M;
		cin >> N;
		cin >> K;
		memset(ary, 0, sizeof(ary));
		memset(chk, 0, sizeof(chk));
		result = 0;
		for (int j = 0; j < K; j++) {
			int x, y;
			cin >> x >> y;
			ary[x][y] = 1;
		}

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (ary[i][j] == 1 && chk[i][j] == 0) {
					chk[i][j] = 1;
					dfs(i, j);
					result++;
				}
			}
		}
		cout << result << endl;
	}

}

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

1. 해결방법

BFS를 통하여 해결하였고, 트리를 Vector에 저장하는 방법을 몰라서 찾아보았다

2. 코드

트리문제 유형을 공부해보지 못해서 고생했다. 특히 비교하는 부분 코드가 수정할 수 있을거 같으므로 나중에 다시 풀어볼 예정이다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N;
int M;
int D;
int root;
int result = 0;
queue<int> q;
vector<int> t[51];

void BFS() {
    if (root == D) return;
    q.push(root);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int i = 0; i < t[node].size(); i++) {
            if (t[node][i] != D) {
                q.push(t[node][i]);
                if (!t[t[node][i]].size() || (t[t[node][i]].size() == 1 &&t[t[node][i]][0] == D)){
                    result++;
                }
            }
            else {
                if (root == node && t[node].size() <=1) result++;
            }
        }
    }
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> M;
        if (M == -1) root = i;
        else t[M].push_back(i);
    }
    cin >> D;
    BFS();
    cout << result;
    return 0;
}

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. 에러 사항

vector를 초기화해주지 않아서 탐색 시간이 길어져 시간 초과가 생겼는데 clear() 함수가 제대로 작동하지 않아서 dfs함수에 vector를 넘겨주고 vector를 전역 변수가 아닌 메인 함수 내부에 선언하는 방식으로 해결하였다

3. 코드

#include<iostream>
#include<vector>
using namespace std;
int test_case;
int T;
int num;
int x, y;
int result = 0;

void vector_dfs(int now, vector<int>* vector){
    if(now == 99){
		result = 1;
        return;
    }else{
        for(int i = 0; i < vector[now].size(); i++){
                        vector_dfs(vector[now][i], vector);    
        }
    }
}

int main(int argc, char** argv)
{
	for(test_case = 1; test_case <= 10; ++test_case)
	{
		cin >> T;
        cin >> num;
		vector<int> vec[100];
        
        for(int i = 0; i < num; i++){
            cin >> x;
            cin >> y;
            vec[x].push_back(y);
        }
        result = 0;
        vector_dfs(0, vec);
            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. 해결방법

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