문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

풀이

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;


int map[26][26] = {0};
int check_map[25][25] = {0};
int num = 1;


bool Ischange = false;
vector<int> res;
int home[626] = { 0 }; 

void DFS(int nowI,int nowJ)
{
	if (map[nowI][nowJ] == 0 || check_map[nowI - 1][nowJ - 1] > 1) //아예 집이없거나 or 확인한적 있거나
		return;
	else
	{
		check_map[nowI - 1][nowJ - 1] = num;
		map[nowI][nowJ] = 0;
		home[num-1]++;
	

		Ischange = true;
		if (map[nowI - 1][nowJ] == 1) //상
			if(check_map[nowI - 2][nowJ-1] < 1)//한번도 check안한 곳
				DFS(nowI - 1, nowJ);
		if(map[nowI + 1][nowJ] == 1)//하
			if (check_map[nowI][nowJ-1] < 1)//한번도 check안한 곳
				DFS(nowI + 1, nowJ);
		if (map[nowI ][nowJ -1] == 1) //좌
			if (check_map[nowI -1][nowJ - 2] < 1)//한번도 check안한 곳
				DFS(nowI , nowJ - 1);
		if (map[nowI ][nowJ +1] == 1)//우
			if (check_map[nowI-1][nowJ] < 1)//한번도 check안한 곳
				DFS(nowI , nowJ+1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int N;
	string input = "0000000";
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> input;
		for (int j = 0; j <N; j++)
		{
			map[i][j+1] = input[j] - '0';
			}
	}
	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			DFS(i, j);
			if (Ischange == true)
			{
				num++; 
				Ischange = false;
			}
		}
	}

	
	num--;

	cout << num<<'\n';
	for (int i = 0; i < num; i++)
		res.push_back(home[i]);

	sort(res.begin(), res.end());

	for (int i = 0; i < res.size(); i++)
		cout << res[i]<<'\n';

	
}

움..일단 DFS로 문제를 풀었고, 배열의 크기때문에 애를 먹었습니다.

000000000
011111110
011111110
011111110
011111110
011111110
011111110
011111110
000000000

이렇게 입력받은값들을 0이라는 벽안에 가둬둘려고했고, 이러면 따로 상하좌우 1이 있는지 검사할때 범위밖으로 나갈일이 없다고 생각을하고 map[26][26]을 했는데.. 제가 생각해놓은걸 구현할려면 [27][27] 이렇게 해야했네요 ㅎㅎㅎ;;

map은[26][26]으로하고, 여길 내가 전에 check했는지를 알기위해 check_map은 또 크기를[25][25]로 했더니 for문 돌릴때도 그렇고 DFS에서 if문으로 체크할때도 꽤나 애먹었습니다. 

그리고 입력받을때 연속된 숫자들(띄어쓰기없이)을 받기때문에 그냥 int형으로 받지않고 문자열로 받되 그 문자열의 문자 하나하나에 '0'을 빼주어 숫자로 배열에 넣어주었습니다.

나름 머리쓴다고 배열의 크기를 생각하다가 제꾀에 제가 넘어간듯한 느낌이었습니다. 그래도 나름 머리에 생각한걸 그대로 표현한것같아서 뿌듯하네요! :D

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

풀이

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int V, E;
vector<pair<long long, pair<int, int>>> edge;
int parents[1000];
int edgenum = 0;

int FindRoot(int x)
{
	if (x == parents[x])
		return x;
	return parents[x] = FindRoot(parents[x]);
}

void Merge(int x, int y)
{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x == y)
		return;
	if (y > x)
		parents[y] = x;
	else
		parents[x] = y;
}





int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	for (int i = 0; i < 1000; i++)
	{
		parents[i] = i;
	}

	int N;
	long long res = 0;
	cin >> N;

	long long input;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++) {
			cin >> input;
			if ((i < j) && (i != j)) {
				edge.push_back({ input,{i,j} });
			}
		}

	}


	sort(edge.begin(), edge.end());

	for (int i = 0; i < edge.size(); i++)
	{
		if (FindRoot(edge[i].second.first) == FindRoot(edge[i].second.second))
			continue;

		Merge(edge[i].second.first, edge[i].second.second);
		res += edge[i].first; 
		edgenum++;

		if (edgenum == N - 1)
			break;

	}
	cout << res<<'\n';
}

이 문제는 같은종류의 문제였던 최소스패닝트리의 전력난과 최소스패닝트리의 문제풀이만을 생각하고있다가 통수맞았습니다! 사실 통수가 아니라 제 지식과 응용의 문제이기도 하겠지만 이전까지 pair<int,pair<int,int>>를 잘 해오다가 이번 문제에서는 똑같이하면 안된다는것을 알았습니다.

위 사진은 각각 다르게 자료형을 가졌을때, sort하고 난 다음의 모습입니다.

vector<pair<long long,pair<int,int>>>로 하였을때는 sort가 cost의 오름차순으로 잘 정렬되어있지만, pair<long long,pair<int,int>> 를 했을 경우에는 중간부터 정렬이 어긋난것을 알 수가 있습니다.

이 원인은 알고보니 sort함수때문에 일어났는데요..제가 바보같이 pair<long long,pair<int,int>>를 했을 당시 sort를 (edge, edge+N)으로 두는 어마어마한 실수를 하였습니다. 분명 마지막 항목은 N이 아니고 그 배일텐데.. 제가  정말 앞에 푼 문제들만 생각하고 심각한 오류를 범했죠..

다행히 Vector<pair<long long,pair<int,int>>>를 했을때는 sort를 sort(edge.bigin(), edge.end())로 두었기에 제가 신경쓰지 않더라도 알아서 잘 정렬을 해주었습니다.

이 글을 쓰면서 다시 한번 쭉 검토해보니 통수가 아니라 정말 바보같은 실수네요! 오랜만에 문제를 풀어보았더니 이런 실수나 하고..부끄럽습니다! 열심히 이제부터 다시 공부해야겠네요 :D

끝만 잘 생각한다면 그냥 크루스칼 알고리즘 그대로 써도 될 정도의 최소스패닝트리 기본문제였습니다.

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

풀이

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<long long> numbers(9000001);
vector<long long> tree(9000001);


long long InitTree(vector<long long>& numbers, vector<long long>& tree, int node, int start, int end)
{

	if (start == end)
		return tree[node] = numbers[start];

	int mid = (start + end) / 2;

	return tree[node] = InitTree(numbers, tree, node * 2, start, mid) +
		InitTree(numbers, tree, node * 2 + 1, mid + 1, end);
}


long long GetPrefixSum(vector<long long>& tree, int node, int start, int end, int left, int right) {
	if (left > end || right < start)
		return 0;
	if (left <= start && end <= right)
		return tree[node];

	int mid = (start + end) / 2;
	return GetPrefixSum(tree, node * 2, start, mid, left, right) +
		GetPrefixSum(tree, node * 2 + 1, mid + 1, end, left, right);
}

void UpdateTree(vector<long long>& tree, int node, int start, int end,
	int index, long long difference) {
	if (!(start <= index && index <= end))
		return;

	tree[node] += difference;

	if (start != end) {
		long long mid = (start + end) / 2;
		UpdateTree(tree, node * 2, start, mid, index, difference);
		UpdateTree(tree, node * 2 + 1, mid + 1, end, index, difference);
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long N, M, K;

	cin >> N >> M >> K;


	for (int i = 1; i <= N; i++)
	{
		cin >> numbers[i];
		
	}

	InitTree(numbers, tree, 1, 1, N);
	int a;
	long long  b, c;
	for (int j = 0; j < M + K; j++)
	{
		cin >> a >> b >> c;
		if (a == 1)
		{
			UpdateTree(tree, 1, 1, N, b, c - numbers[b]);
			numbers[b] = c;
		}
		else if (a == 2)
		{
			cout<<GetPrefixSum(tree, 1, 1, N, b, c)<<'\n';
		}
	}


}

이 문제는 처음에 세그먼트 트리를 그냥 바로 쓰면 되는줄 알고 단순하게 생각하고 통수 7번 맞은 문제입니다. 심지어 맞추고 나서도 통수 2번 더 맞았습니다.

처음 메모리초과는 입력받는 정수와 벡터의 자료형을 int로 하여서 많이 떳습니다. => 결국 정답은 long long

그 다음에는 여러군데 많이 고쳐줘서 맞았습니다.가 떳지만 너무 많이 고쳤기에 어느 부분때문에 맞은건지를 잘 몰라서

정답을 맞췄음에도 불구하고 정답률을 낮추기위해 한 몸 희생해서 제출을 더해보았습니다.

런타임에러는 벡터의 크기를 작게 잡았기때문에 떳습니다. => 해결은 벡터 크기 늘리기 

틀렸습니다는 출력할때 '\n' 개행문자를 안넣어줘서 떳습니다. =>해결은 개행문자 넣기

참 여러방면으로 다양하게 틀려줬습니다. 

만약 게임이었으면 타이틀 모으는 재미라도 있었을텐데..

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

풀이

#include<iostream>
#include<algorithm>
using namespace std;


int m, n;

pair<long, pair<int, int>> edge[200001];
int parents[200001];

long res=0;
int edgenum = 0;


int FindRoot(int x)
{
	if (x == parents[x])
		return x;
	return parents[x] = FindRoot(parents[x]);
}

void Merge(int x, int y)
{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x == y)
		return;
	parents[x] = y;
}


int main()
{


	int x, y, z;


	while(1)
	{
		edgenum = 0;
		res = 0;


		cin >> m >> n;

		
		if (m == 0 && n == 0)
			break;


		for (int i = 0; i <= n; i++)
		{
			parents[i] = i;
			edge[i] = { 0,{0,0} };
		}



		for (int i = 0; i < n; i++) 
		{
			cin >> x >> y >> z;

			edge[i] = { z,{x,y} };
			res += z;

		}


		sort(edge, edge + n);


		for (int i = 0; i < n; i++)
		{
			if (FindRoot(edge[i].second.first) == FindRoot(edge[i].second.second))
				continue;

			Merge(edge[i].second.first, edge[i].second.second);
			res -= edge[i].first;

			edgenum++;
			if (edgenum == m - 1)
				break;
		}

		cout << res<<'\n';


	}

}

위의 문제에서 입력부분을 잘 보면  "입력은 여러 개의 테스트 케이스로 구분되어 있다." 라는 말이 있습니다.

네, 이 말 때문에 몇번 틀렸습니다. 

저는 백준문제들의 정답비율을 낮추는데에 한번 더 공헌을 했습니다.

입력받는 부분을 무한반복문으로 돌리면서 0,0을 입력받으면 끝나게 해야합니다. 저는 오히려 "도시상의 모든 길의 거리 합은 231미터보다 작다." 같은 자료형 범위를 유심히 살피다가 오히려 근본적인 문제에서부터 잘못된거죠..(´。＿。｀)..

그래도 푸는데 따로 어려운점은 없었습니다. 바로 직전에 풀었던 최소스패닝트리와 매우 유사합니다.

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