잡다한 프로그래밍

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;
}