#include <iostream>  
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
 
using namespace std;
 
int N, M, number;
int DirX[4] = { 1, -1, 0, 0 };
int DirY[4] = { 0, 0, 1, -1 };
 
int arr[11][11];
int check[11][11];
int visit[7];
int parent[7];
 
vector<tuple<int, int, int>> vec;
vector<int> graph[7];
 
bool cmp(tuple<int, int, int> dist1, tuple<int, int, int> dist2)
{
    if (get<2>(dist1) == get<2>(dist2))
    {
        if (get<0>(dist1) == get<0>(dist2))
            return get<1>(dist1) < get<1>(dist2);
 
        else
            return get<0>(dist1) < get<0>(dist2);
    }
 
    else
        return get<2>(dist1) < get<2>(dist2);
}
 
int FindParent(int x)
{
    if (parent[x] == x)
        return x;
 
    else
        return parent[x] = FindParent(parent[x]);
}
 
bool ParentCheck(int x, int y)
{
    x = FindParent(x);
    y = FindParent(y);
 
    if (x == y)
        return true;
 
    else
    {
        parent[y] = x;
 
        return false;
    }
}
 
void DFS(int x, int y)
{
    if (check[x][y])
        return;
 
    check[x][y] = true;
    arr[x][y] = number;
 
    for (int i = 0; i < 4; ++i)
    {
        int nextX = x + DirX[i];
        int nextY = y + DirY[i];
 
        if (nextX >= 0 && nextX < N &&
            nextY >= 0 && nextY <= M)
        {
            if (arr[nextX][nextY] && !check[nextX][nextY])
            {
                DFS(nextX, nextY);
            }
        }
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (arr[i][j])
            {
                if (!check[i][j])
                    ++number;
 
                DFS(i, j);
            }
        }
    }
 
    for (int i = 1; i <= number; ++i)
    {
        parent[i] = i;
    }
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (arr[i][j])
            {
                for (int z = 0; z < 4; ++z)
                {
                    int x = i;
                    int y = j;
                    int dist = 0;
 
                    while (true)
                    {
                        x += DirX[z];
                        y += DirY[z];
 
                        if (x < 0 || x > N || y < 0 || y > M || arr[x][y] == arr[i][j])
                            break;
 
                        if (arr[x][y])
                        {
                            vec.push_back({ arr[i][j], arr[x][y], dist });
                            break;
                        }
 
                        ++dist;
                    }
                }
            }
        }
    }
 
    sort(vec.begin(), vec.end(), cmp);
 
    int ans = 0;
 
    for (int i = 0; i < vec.size(); ++i)
    {
        int x = get<0>(vec[i]);
        int y = get<1>(vec[i]);
        int dist = get<2>(vec[i]);
 
        if (dist < 2) 
            continue;
 
        if (!ParentCheck(x, y))
        {
            graph[x].push_back(y);
            graph[y].push_back(x);
 
            ans += dist;
        }
    }
 
    int count = 1;
    queue<int> que;
    que.push(1);
 
    while (!que.empty())
    {
        int now = que.front();
        que.pop();
        visit[now] = true;
 
        for (int i = 0; i < graph[now].size(); ++i)
        {
            int next = graph[now][i];
 
            if (!visit[next])
            {
                que.push(next);
                ++count;
            }
        }
    }
 
    if (count != number)
        cout << -1;
 
    else
        cout << ans;
 
    return 0;
}

부모를 찾아서 하나로 연결을 시켜야하는 알고리즘입니다.

선을 만드는 게 관건이었는데 한 개의 섬을 DFS로 모든 위치를 같은 번호로 바꿉니다.

그렇게 된다면 섬이 어디에 있는지 얼마나 거리가 차이나는지 확인 할 수 있습니다.

최대 크기가 크지 않기 때문에 모든 위치에서 모든 방향으로 확인을 해서 거리를 구합니다.

그 거리를 vec에 넣어서 가장 짧은 선으로 부모를 확인합니다.

'오늘의 알고리즘' 카테고리의 다른 글

[C++] 백준 4195 친구 네트워크  (0) 2023.05.15
[C++] 백준 11780 플로이드 2  (0) 2023.05.12
[C++] 백준 1450 냅색문제  (0) 2023.05.08
[C++] 백준 9370 미확인도착지  (0) 2023.05.03
[C++] 백준 1956 운동  (0) 2023.05.02
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <string>
 
using namespace std;
 
int parent[200001];
int friendcount[200001];
 
int FindParent(int now)
{
	if (now == parent[now])
		return now;
 
	else
		return parent[now] = FindParent(parent[now]);
}
 
void SetParent(int now, int set)
{
	int x = FindParent(now);
	int y = FindParent(set);
 
    if (x < y) 
    {
        parent[y] = x;
        friendcount[x] += friendcount[y];
    }
 
    else if (x > y) 
    {
        parent[x] = y;
        friendcount[y] += friendcount[x];
    }
}
 
using namespace std;
 
int arr[100001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n = 0;
    cin >> n;
 
    while (n--)
    {
        int F = 0;
        cin >> F;
 
        for (int i = 0; i < 200001; ++i)
        {
            parent[i] = i;
            friendcount[i] = 1;
        }
 
        int count = 0;
 
        unordered_map<string, int> unmap = {};
 
        for (int i = 0; i < F; ++i)
        {
            int friendnum1 = 0;
            int friendnum2 = 0;
            string s1, s2;
            cin >> s1 >> s2;
 
            if (unmap[s1])
            {
                friendnum1 = unmap[s1];
            }
 
            else 
            {
                unmap[s1] = ++count;
                friendnum1 = count;
            }
 
            if (unmap[s2])
            {
                friendnum2 = unmap[s2];
            }
 
            else 
            {
                unmap[s2] = ++count;
                friendnum2 = count;
            }
 
            SetParent(friendnum1, friendnum2);
 
            cout << friendcount[FindParent(friendnum1)] << '\n';
        }
    }
 
    return 0;
}

이름으로 본인의 순서를 찾아내고 그 숫자를 parent로 본인의 숫자로 합쳐서 찾습니다.

 

'오늘의 알고리즘' 카테고리의 다른 글

[C++] 백준 17472 다리 만들기 2  (0) 2023.05.19
[C++] 백준 11780 플로이드 2  (0) 2023.05.12
[C++] 백준 1450 냅색문제  (0) 2023.05.08
[C++] 백준 9370 미확인도착지  (0) 2023.05.03
[C++] 백준 1956 운동  (0) 2023.05.02

 

#include <iostream>
#include <vector>
#include <algorithm>
 
#define MAX 10000001
using namespace std;
 
int arr[101][101];
int mid[101][101];
 
int main() 
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            arr[i][j] = MAX;
        }
    }
 
    for (int i = 0; i < m; ++i)
    {
        int start, end, cost;
        cin >> start >> end >> cost;
 
        arr[start][end] = min(arr[start][end], cost);
        mid[start][end] = end;
    }
 
    for (int z = 1; z <= n; ++z)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (i == j) 
                    continue;
 
                if (arr[i][j] > arr[i][z] + arr[z][j])
                {
                    arr[i][j] = arr[i][z] + arr[z][j];
                    mid[i][j] = mid[i][z];
                }
            }
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (arr[i][j] == MAX) 
                cout << "0 ";
 
            else 
                cout << arr[i][j] << " ";
        }
 
        cout << "\n";
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (arr[i][j] == MAX)
            {
                cout << "0\n";
                continue;
            }
 
            vector<int> vec;
            int now = i;
 
            while (now != j) 
            {
                vec.push_back(now);
                now = mid[now][j];
            }
 
            vec.push_back(now);
 
            cout << vec.size() << ' ';
 
            for (int now : vec)
            {
                cout << now << ' ';
            }
 
            cout << '\n';
        }
    }
 
    return 0;
}

플로이드 와샬 문제라서 i,j,z로 회전하면서 최저의 길이를 구합니다.

하지만 이 문제는 최저의 길이의 중간 도착지를 알아야 하기 때문에

플로이드와샬을 알고리즘을 실행하면서 더 작은 길이가 있다면 중간점을 따로 저장합니다.

중간점을 계속해서 들어가면서 현재점까지 찾아옵니다.

 

'오늘의 알고리즘' 카테고리의 다른 글

[C++] 백준 17472 다리 만들기 2  (0) 2023.05.19
[C++] 백준 4195 친구 네트워크  (0) 2023.05.15
[C++] 백준 1450 냅색문제  (0) 2023.05.08
[C++] 백준 9370 미확인도착지  (0) 2023.05.03
[C++] 백준 1956 운동  (0) 2023.05.02
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<long long>  vec;
 
void dfs(int start, int end, vector<long long>& part, long long sum) 
{
	if (start > end) 
	{
		part.push_back(sum);
		return;
	}
 
	else 
	{
		dfs(start + 1, end, part, sum);
		dfs(start + 1, end, part, sum + vec[start]);
	}
}
int main() 
{
	int N, C; 
	cin >> N >> C;
 
	vec = vector<long long>(N, 0);
 
	for (int i = 0; i < N; ++i)
	{
		cin >> vec[i];
	}
 
	vector<long long> left;
	vector<long long> right;
 
	dfs(0, N / 2 - 1, left, 0);
	dfs(N / 2, N - 1, right, 0);
 
	sort(right.begin(), right.end());
 
	int count = 0;
 
	for (int i = 0; i < left.size(); ++i)
	{
		count += upper_bound(right.begin(), right.end(), C - left[i]) - right.begin();
	}
 
	cout << count;
 
	return 0;
}

이게 왜 투포인터인가... 싶은 느낌의 문제였는데

모든 수를 넣었다 뺏다 하려니까 2의 30승으로 시간이 모자르더라구요.

최대를 반으로 나눠서 시간을 나눴습니다. 최대를 2의 15승 두번으로 나눴습니다.

이후 갯수를 세주는 upper_bound로 왼쪽과 오른쪽의 합이 C를 넘지 않는 경우를 구해서 count에 더해줍니다.

'오늘의 알고리즘' 카테고리의 다른 글

[C++] 백준 4195 친구 네트워크  (0) 2023.05.15
[C++] 백준 11780 플로이드 2  (0) 2023.05.12
[C++] 백준 9370 미확인도착지  (0) 2023.05.03
[C++] 백준 1956 운동  (0) 2023.05.02
[C++] 백준 11657 타임머신  (0) 2023.05.01

+ Recent posts