Posted 2021-08-01Updated 2021-03-16algorithm3 minutes read (About 464 words)

Graph B1167

개요

백준 문제 1167번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 2시간
https://www.acmicpc.net/problem/1167

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

계획한 풀이법

처음엔 간단히 생각해서 그냥 입력받은 뒤 DFS하면 될 줄 알았지만
그렇지 않았다 왜냐하면 DFS는 가장 깊게 들어가게 되는데, 이 때 끝점과 시작점까지의 길이가 가장 긴 길이라고는 단정할 수 없다.
가중치는 가장 큰 값인 것이 분명하지만, 그것과 별개로 현재 시작점과 가중치가 가장 큰 정점이 가장 길지 않는 경우도 있기 때문이다.
그렇다면 가중치가 가장 높은 정점에서 DFS를 하게 되면 이때는 가중치가 가장 큰 정점이 시작점이니 여기서도 가장 큰 길이가 나오게 된다.

코드

#include <iostream>
#include <vector>

using namespace std;
const int MAX = 100001;

vector<pair<int, int> > graph[MAX];
bool visit[MAX];
int maxCost = 0;
int maxCostNode = 0;

int DFS(int startV,int cost)
{
	if(visit[startV])
	{
		return -1;
	}
	int result;
	visit[startV] = true;

	for(int i=0;i<graph[startV].size();i++)
	{	
		result = DFS(graph[startV][i].first,graph[startV][i].second+cost);
		if(result > maxCost)
		{
			maxCost = result;
			maxCostNode = graph[startV][i].first;
		}
	}
	return cost;

}

void connectEdge(int v,int e,int length)
{
	graph[v].push_back(make_pair(e,length));
}

void solve()
{

	int N = 0;
	cin >> N;

	int v = 0,e = 0,len = 0;
	for(int i=0;i<N;i++)
	{
		v = 0,e = 0,len = 0;
		cin >> v >> e;

		while(e != -1)
		{
			cin >> len;
			connectEdge(v,e,len);
			cin >> e;
			
		}
	}

	fill_n(visit,MAX,false);

	for(int i=1;i<=N;i++)
	{
		DFS(i,0);
	}
	maxCost = 0;
	fill_n(visit,MAX,false);
	DFS(maxCostNode,0);


	cout << maxCost;

}

int main()
{
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	solve();

}

느낀 점

이 문제는 다른 사람의 풀이를 참조하고 이해하여 문제를 풀었다.
문제를 읽고 떠오른 방법에 대한 검증을 깊게 해보자(너무 단순하게 생각하지 말자)

Posted 2021-08-01Updated 2021-03-16algorithm2 minutes read (About 360 words)

Graph B11725

개요

백준 문제 11725번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 35분
https://www.acmicpc.net/problem/11725

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

계획한 풀이법

문제를 보고 루트 없는 트리가 주어진다길래 무슨 말인가 했는데
루트를 1이라고 생각하고 입력이 주어진다는 말이었다.
풀이는 어쨌거나 트리는 최상위 루트가 존재해야하는데 그것이 1로 주어진다고 하여서 이를 힌트로 삼았다.
기준을 1로(시작점) 잡으면 그 이후 부터는 BFS로 이동하기 전 노드가 이동하려는 노드의 부모 노드가 되니 이를 마킹하면 되는 문제이다.

코드

//PM 6:17
// 구상~ 
//PM 6:34
// 구현~
//PM 6:55
//완

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 100001;

vector<int> graph[MAX];
int visit[MAX];
int N;

void init()
{
	cin >> N;
	for(int i=0;i<N+1;i++)
	{
		visit[i] = 0;
	}
}

void edgeBiConnect(int v,int e)
{
	graph[v].push_back(e);
	graph[e].push_back(v);


}
//루트가 있을때 root -> e
void edgeOneConnect(int v)
{
	graph[1].push_back(v);
}

void BFS(int startV)
{
	queue<int> q;
	int curV;


	for(int i=0;i<graph[1].size();i++)
	{
		q.push(graph[1][i]);
		visit[graph[1][i]] = 1;
	}

	while(q.size() != 0)
	{
		curV = q.front();
		q.pop();

		for(int i=0;i<graph[curV].size();i++)
		{

			if(visit[graph[curV][i]] == 0)
			{
				q.push(graph[curV][i]);
				visit[graph[curV][i]] = curV;
			}
			
		}
	}


}

void solve()
{
	int v,e;
	for(int i=0;i<N;i++)
	{
		cin >> v >> e;
		if(v == 1)
		{
			edgeOneConnect(e);
		}
		else if(e == 1)
		{
			edgeOneConnect(v);
		}
		else
		{
			edgeBiConnect(v,e);
		}
	}
	BFS(1);
	for(int i=2;i<=N;i++)
	{
		cout << visit[i] << "\n";
	}
}


int main()
{
	init();
	solve();

}

느낀 점

문제 자체는 쉬웠으나 한번에 고민한 것이 맞았고 코드도 나름 간결하게 짠 것 같아 만족한 풀이

Posted 2021-08-01Updated 2021-03-16algorithm2 minutes read (About 363 words)

Graph B1991

개요

백준 문제 1991번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 1시간
https://www.acmicpc.net/problem/1991

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

계획한 풀이법

풀이 방법)

트리 생성
전위,중위,후위 순회를 재귀로 구현

코드

#include <iostream>

using namespace std;

int tree[26][2];

void init()
{
	int n = 0;
	char rootVal,leftVal,rightVal;
	cin >> n;
	for(int i=0;i<n;i++)
	{
		cin >> rootVal >> leftVal >> rightVal;
		tree[rootVal-'A'][0] = leftVal;	
		tree[rootVal-'A'][1] = rightVal;
	}
}

void preOrder(char root)
{
	if(root == '.')
	{
		return;
	}
	cout << root;
	preOrder(tree[root-'A'][0]);
	preOrder(tree[root-'A'][1]);
}

void inOrder(char root)
{
	if(root == '.')
	{
		return;
	}
	inOrder(tree[root-'A'][0]);
	cout << root;
	inOrder(tree[root-'A'][1]);
}

void postOrder(char root)
{
	if(root == '.')
	{
		return;
	}
	postOrder(tree[root-'A'][0]);
	postOrder(tree[root-'A'][1]);
	cout << root;
}


void solve()
{
	preOrder('A');
	cout << "\n";
	inOrder('A');
	cout << "\n";
	postOrder('A');


}

int main()
{
	init();
	solve();

}

막혔던 점

위 코드는 다른사람의 코드를 보고나니 내 코드가 너무 안쓰러워서 다시 수정한 코드이다.
연결리스트로 구현을 할려고 했는데, 입력을 한줄 씩 받으면서 재귀로 트리를 구성할려고 하니 N만큼 입력받는게
전역함수를 추가하는 등 코드가 더러웠는데 역시 많이 상황에서 배열이 간단한 코드를 구성하는데 도움이 되는 것 같다.

느낀 점

코드를 쉽게 짜려는 것에 중점을 두자

Posted 2021-08-01Updated 2021-03-18algorithm5 minutes read (About 739 words)

Graph B1967

개요

백준 문제 1967번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 2시간
https://www.acmicpc.net/problem/1967

문제

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

계획한 풀이법

이전에 푼 문제와 사실상 똑같은 문제였다.
비교대상은 무엇이든 상관없으니 1로 시작하도록 하고 가장 가중치가 큰 정점을 찾아
그 정점을 DFS하면 최대 길이가 나오게 된다.

코드

#include <iostream>
#include <vector>
#include <stack>



using namespace std;
const int MAX = 10001;
//메모리 초과
vector<pair<int,int>> graph[MAX];
int N = 0;
bool visit[MAX];
int maxCost = 0;

int DFS(int startV)
{
	stack<pair<int,int>> s;
	s.push(make_pair(startV,0));
	int curV = 0;
	bool allVisited = false;
	int curCost = 0;
	int maxV = 0;

	while(s.size() != 0)
	{
		curV = s.top().first;
		if(!visit[curV])
		{
			curCost += s.top().second;

		}
		visit[curV] = true;
		allVisited = true;
		if(maxCost < curCost)
		{
			maxCost = curCost;
			maxV = curV;
		}
		for(int j=0;j<graph[curV].size();j++)
		{
			int nextV = graph[curV][j].first;
			if(visit[nextV])
			{
				continue;
			}
			int prevCost = graph[curV][j].second;
			s.push(make_pair(nextV, prevCost));
			allVisited = false;
			break;
		}
		if(allVisited)
		{
			curCost -= s.top().second;
			s.pop();
		}

	}
	return maxV;



}

void connectEdge(int v,int e,int cost)
{
	//cout << "V , E 연결\n";
	//cout << v << "," << e << "\n";

	graph[v].push_back(make_pair(e,cost));
	graph[e].push_back(make_pair(v,cost));

}

void init()
{
	cin >> N;
	int v,edge,cost;
	for(int i=0;i<N-1;i++)
	{
		cin >> v >> edge >> cost;
		connectEdge(v,edge,cost);
	}

}

void solve()
{
	int maxV = DFS(1);
	fill_n(visit,MAX,0);
	DFS(maxV);
	cout << maxCost;
}


int main()
{
	init();
	solve();




}

느낀 점

2시간 넘겨서 참고한 풀이가 바로 생각났는데 이래서는 내가 푼게 아닌 것 같은 기분이 들었다.
하지만 여러가지 시도를 해보니 이 방법이 맞구나 체감이 되어서 곧 바로 풀었다.
또 고집이 문제 풀이 시간을 눌렸다.
스스로가 생각한 풀이방법으로 풀린다면 얼마나 좋을까?
하지만 그렇지 않은 경우가 앞으로 엄청나게 많을 것이다.
그렇다고 기죽을 필요는 없는 것 같다.
당연히 내가 잘하는 사람이 되기 전까지는 그 사람들의 뒷모습을 보는 것이 당연한 것이다.
불만있으면 내가 잘하는 사람이 될때까지 더 열심히 해야 한다
지금은 결과주의자가 되자 문제를 빠르게 맞추는 것에만 집중하자
아직은 직관을 배워야 할 것 같다.

Graph B1167

개요

문제

계획한 풀이법

코드

느낀 점

Graph B11725

개요

문제

계획한 풀이법

코드

느낀 점

Graph B1991

개요

문제

계획한 풀이법

코드

막혔던 점

느낀 점

Graph B1967

개요

문제

계획한 풀이법

코드

느낀 점

Categories

Recents

Archives

Tags

Subscribe for updates