코딩생존기

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

삼각형을 2차원 벡터를 통해 입력받고 이 벡터와 크기가 같은 벡터를  선언해주고 이 벡터에 누적합을 계산해서 넣어주면 된다. 이때 현재 층에서 내려갈 때 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서 선택해서 내려가야하는데  내려가있는 입장에서 생각해보면 경우를 나눠서 계산을 해줘야한다.

가장 왼쪽의 경우에는 x-1, y 위치의 원소에 자신의 값을 더해주면 된다.

가장 오른쪽의 경우에는 x-1, y-1 위치의 값에 자신의 값을 더해주면 된다.

가운데의 경우에는  x-1,y-1 와 x-1,y위치 중에 큰 값과 자신의 값을 저해주면 된다.

마지막행에서 최대값을 찾아서 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> triangle(n, vector<int>(n, 0));


	for (int i = 0; i < n; i++)
	{
		for (int j =0; j<=i; j++)
		{
			cin >> triangle[i][j];
		}
		
	}
	
	vector<vector<int>> dp(n, vector<int>(n, 0));

	dp[0][0] = triangle[0][0];

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			//가장 왼쪽
			if (j == 0)
			{
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i)	//가장 오른쪽
			{
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else      //가운데
			{
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		result = max(dp[n - 1][i], result);
	}

	cout << result << "\n";
}

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

먼저 모든 집의 RGB에 해당하는 비용 값을 벡터를 통해 입력받고 n-1까지의 합벡터를 채워주면 되는데 이때 RGB를 더할 때 문제에서 각 집을 칠할 때 이전 집과 같은 색을 사용할 수 없으므로, 이 조건을 만족하며 비용을 최소화하는 선택만을 하도록 하여 자신을 제외한 이전에 계산된 비용중에서 최소값과 자신의 비용을 더한 것이 현재 위치의 합 배열이 값으로 계산해주면 된다.

정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> cost(n, vector<int>(3));
	vector<vector<int>> dp(n, vector<int>(3));

	//RGB입력받기
	for (int i = 0; i < n; i++)
	{
		cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
	}

	// 첫 번째 집 초기화
	dp[0][0] = cost[0][0];
	dp[0][1] = cost[0][1];
	dp[0][2] = cost[0][2];

	//미리 모든 경우의수 계산
	for (int i = 1; i < n; i++)
	{
		dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
		dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
		dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
	}

	int result = min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] });
	cout << result << endl;

	return 0;
}

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

케이스 수만큼 반복을 해주는데 이때 그래프 크기를 입력받고 이에 맞게 assign함수를 통해 벡터를 m,n의 크기로 초기화해주고 배추가 있는 부분만 1로 수정해준다. 그리고 그래프를 전체 순회하면서 1인부분을 만난다면 BFS방식으로 순회하면서 방문처리를 해준다. 그리고 모두 방문처리가 완료되면 true를 반환해서 result값을 1 더해주고 이 result에 1이 몇번 더해졌는지 출력해주면 된다. 

정답코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
bool BFS(int x, int y);
vector<vector<int>> graph;
vector < vector<bool> >visited;
int main()
{
	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		m = 0, n = 0;
		int k;

		cin >> m >> n >> k;

		graph.assign(m, vector<int>(n, 0));
		visited.assign(m, vector<bool>(n, false));

		//배추 입력
		for (int i = 0; i < k; i++)
		{
			int X, Y;
			cin >> X >> Y;

			graph[X][Y] = 1;
		}

		int result = 0;

		//그래프 순회
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (graph[i][j] == 1 && !visited[i][j])
				{
					if (BFS(i, j)) result++;
				}
			}
		}

		cout << result << "\n";
	}
}

bool BFS(int x, int y)
{
	//상하좌우
	int nx[4] = { -1,1,0,0 };
	int ny[4] = { 0,0,-1,1 };

	queue<pair<int, int>> q;
	q.push({ x,y });
	visited[x][y] = true;

	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + nx[i];
			int next_y = cur_y + ny[i];

			if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n)
			{
				if (graph[next_x][next_y] == 1 && !visited[next_x][next_y])
				{
					visited[next_x][next_y] = true;
					q.push({ next_x,next_y });
				}
			}
		}
	}

	return true;
}

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

그래프를 입력받고 그래프 전체를 순회하는데 방문하지 않았고 1이라면 집이 있기 때문에 여기서부터 BFS방식으로 순회하면서 더 이어진 주택이 없을 때까지 순회한다. 그리고 이 과정에서 들린 집개수를 카운트해서 반환해주면 된다.

정답코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n;
int BFS(int x,int y);
vector<vector<int>> house;
vector<vector<bool>> visited;
int main()
{
	cin >> n;

	house.resize(n, vector<int>(n));
	visited.resize(n, vector<bool>(n,false));

	//그래프 입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			char c;
			cin >> c;
			//문자열-> 숫자
			house[i][j] = c - '0';
		}
	}

	vector<int> answer;

	//그래프 순회
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j] && house[i][j] == 1)
			{
				int h_cnt = BFS(i, j);
				answer.push_back(h_cnt);
			}
		}
	}
	
	//오름차순 정렬
	sort(answer.begin(), answer.end());
	cout << answer.size() << "\n";
	for (int i = 0; i < answer.size(); i++)
	{
		cout << answer[i] << "\n";
	}
}

int BFS(int x,int y)
{
	//상하좌우
	int nx[4] = { -1,1,0,0 };
	int ny[4] = { 0,0,-1,1 };

	queue<pair<int, int>> q;


	q.push({ x,y });
	visited[x][y] = true;

	int cnt = 1;

	//현재위치에서 이어져 있는 주택이 있으면 연결
	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + nx[i];
			int next_y = cur_y + ny[i];

			if (next_x >= 0 && next_x < n && next_y>=0 && next_y < n)
			{
				if (house[next_x][next_y] == 1 && !visited[next_x][next_y])
				{
					q.push({ next_x,next_y });
					visited[next_x][next_y] = true;
					cnt++;
				}
			}
		}
	}

	return cnt;	
}

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

그래프입력을 받고 DFS를 통해 순회하면서 시작노드를 제외하고 전역변수를 통해 카운트하면서 얼마나 순회하는지 계산하면 된다. 

정답코드

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


void DFS(int node);
vector<vector<int>> computers;
vector<bool> visited;
int cnt = 0;
int main()
{
	int n, m;
	cin >> n >> m;

	computers.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		computers[u].push_back(v);
		computers[v].push_back(u);
	}

	DFS(1);

	cout << cnt << "\n";
}

void DFS(int node)
{
	visited[node] = true;
	
	for (int i : computers[node])
	{
		if (!visited[i])
		{
			cnt++;
			DFS(i);
		}
	}
}

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

그래프 입력을 받고 각 정점벡터를 내림차순으로 정렬한 다음에 의사코드에 나와있는 코드와 같이 구현해준다.

이때 전역변수를 사용하여 방문순서를 기록해주도록 하자.

정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void DFS(int node);
vector<vector<int>> graph;
vector<int> visited;
int order = 1;
int main()
{
	int n, m, r;
	cin >> n >> m >> r;

	graph.resize(n + 1);
	visited.resize(n + 1);
	fill(visited.begin(), visited.end(), 0);

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// 인접 정점 내림차순으로 정렬
	for (int i = 1; i <= n; i++) {
		sort(graph[i].rbegin(), graph[i].rend());
	}

	DFS(r);

	for (int i = 1; i <= n; i++)
	{
		cout << visited[i] << "\n";
	}
}

void DFS(int node)
{
	visited[node] = order++;
	for (int next : graph[node]) {
		if (!visited[next]) {
			DFS(next);
		}
	}
}

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

A번째 도시에서 B번째 도시까지 최소 비용을 출력해줘야한다. 다익스트라 알고리즘을 가지고 풀어보았다. 우선 시작점에서 모든 경로로 가는 최소비용을 계산해두고 계산된 도착지까지의 최소 비용을 출력해주면 된다. 

다익스트라 계산과정에서 priority_queue를 사용하는 이유는, 다익스트라 알고리즘에서 가장 짧은 경로를 가진 정점을 빠르게 선택하기 위해서이다.

정답코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

typedef pair<int, int> edge;
//인접그래프
vector<vector<edge>> graph;
//거리
vector<int> mdistance;
//방문여부
vector<bool> visited;

int dijkstra(int start, int end);

int  main()
{
	int v, e;

	cin >> v >> e;

	graph.resize(v + 1);
	mdistance.resize(v + 1);
	fill(mdistance.begin(), mdistance.end(), INT_MAX);
	visited.resize(v + 1);
	fill(visited.begin(), visited.end(), false);

	//그래프 입력받기
	for (int i = 0; i < e; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back(make_pair(v, w));
	}

	int start, end;
	cin >> start >> end;

	cout << dijkstra(start, end) << endl;

	return 0;
}

int dijkstra(int start, int end)
{
	//방문할 노드(거리, 노드)
	priority_queue < edge, vector<edge>, greater<edge>> pq;

	//처음 시작점과 거리값 넣기
	pq.push(make_pair(0, start));
	mdistance[start] = 0;
	//다익스트라 계산
	while (!pq.empty())
	{
		//현재 위치노드 가져오기
		int cur_v = pq.top().second;
		pq.pop();
		//방문했다면 넘어가기
		if (visited[cur_v]) continue;

		visited[cur_v] = true;

		//현재 위치에서 연결된 노드 순회
		for (edge i : graph[cur_v])
		{
			int next_v = i.first;
			int next_e = i.second;

			//현재 거리보다 짧은 거리가 나오면 바꾸기
			if (mdistance[next_v] > mdistance[cur_v] + next_e)
			{
				mdistance[next_v] = mdistance[cur_v] + next_e;
				pq.push(make_pair(mdistance[next_v], next_v));
			}
		}
	}

	return mdistance[end];
}

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

시작점에서 다른 모든 정점으로 가는 최단경로를 구하는 문제로 다익스트라 알고리즘을 활용하여 풀어보았다. 처음에 

거리벡터를 모두 무한대로 초기설정을 해준 다음 모든 노드를 BFS 방식으로 순회하면서 최소값으로 갱신해나간 다음 

최종 거리 벡터를 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

typedef pair<int, int> edge;
//인접그래프
vector<vector<edge>> graph;
//거리
vector<int> mdistance;
//방문여부
vector<bool> visited;
//방문할 노드(거리, 노드)
priority_queue < edge, vector<edge>, greater<edge>> pq;
int  main()
{
	int v, e, s;

	cin >> v >> e >> s;

	graph.resize(v + 1);
	mdistance.resize(v + 1);
	fill(mdistance.begin(), mdistance.end(), INT_MAX);
	visited.resize(v + 1);
	fill(visited.begin(), visited.end(), false);

	//그래프 입력받기
	for (int i = 0; i < e; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;

		graph[u].push_back(make_pair(v, w));
	}

	//처음 시작점 넣기
	pq.push(make_pair(0, s));
	mdistance[s] = 0;
	//다익스트라 계산
	while (!pq.empty())
	{
		int cur_v = pq.top().second;
		pq.pop();
		if (visited[cur_v]) continue;

		visited[cur_v] = true;

		for (edge i : graph[cur_v])
		{
			int next_v = i.first;
			int next_e = i.second;

			//현재 거리보다 짧은 거리가 나오면 바꾸기
			if (mdistance[next_v] > mdistance[cur_v] + next_e)
			{
				mdistance[next_v] = mdistance[cur_v] + next_e;
				pq.push(make_pair(mdistance[next_v], next_v));
			}
		}
	}

	for (int i = 1; i <= v; i++)
	{
		if(visited[i])
		{
			cout << mdistance[i] << "\n";
		}
		else
		{
			cout << "INF" << "\n";
		}
		
	}

}

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

이 문제는 먼저 지어야하는 건물이 있는 경우가 존재하고 이를 통해 건물 간의 건설 순서를 정해 주어야하는데 이때

위상정렬을 통해 풀 수 있다. 계산 과정에서 중요한 점은 아래와 같은 코드인데

answer[i] = max(answer[i], answer[cur] + apart_time[cur])

cout << answer[i] + apart_time[i] << "\n";

answer[i]는 건물 i를 짓기까지 걸린 총 시간으로 answer[cur] + apart_time[cur]는 현재 건물 cur까지 짓는 데 걸린 시간에 현재 건물의 건축 시간을 더한 것으로 이전까지 계산된 answer[i] 값과 현재 건물 cur을 통한 경로로부터의 시간 중 더 큰 값을 선택하기 위한 코드이고 

마지막에 출력하는 부분은 건물 i를 짓기 위해 필요한 모든 선행 건물들이 지어지는 데 걸린 누적 시간이고 실제로 건물 i를 짓는 시간이므로, 최종적으로 두 값을 더해줘야 건물 i가 완성되는 데 걸린 총 시간을 계산할 수 있다.

정답코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> apartments;
vector<int> apart_time;
vector<int> indegree;		//진입 차수배열
int main()
{
	int n;
	cin >> n;

	apartments.resize(n + 1);
	apart_time.resize(n + 1);
	indegree.resize(n + 1);

	//각 건물정보 입력
	for (int i = 1; i <= n; i++)
	{
		//각 시간 입력
		cin >> apart_time[i];

		//먼저 지어야하는 건물 입력
		while (true)
		{
			int apt;
			cin >> apt;

			if (apt == -1) break;
			
			apartments[apt].push_back(i);
			indegree[i]++;
		}
	}

	queue<int> q;

	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 0)
			q.push(i);
	}

	vector<int> answer;
	answer.resize(n + 1);

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i : apartments[cur])
		{
			indegree[i]--;
			//기존 값 vs 선행 건물 시간추가 
			answer[i] = max(answer[i], answer[cur] + apart_time[cur]);
			if (indegree[i] == 0)
			{
				q.push(i);
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cout << answer[i] + apart_time[i] << "\n";
	}
}

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

케이스에따라 그래프를 입력받고 DFS 방식으로 그래프를 순회하면서 노드마다 다른 집합에 저장하고 순회 중에

시작 노드와 같은 집합인 vertex가 있으면 사이클이 생기기 때문에 이분 그래프가 안되는 것이다. 

정답코드

#include <iostream>
#include <vector>

using namespace std;

void DFS(int node);

vector<vector<int>> graph;
vector<int> check;
vector<bool> visited;
bool isEven;

int main()
{
	int k;
	cin >> k;

	for (int i = 0; i < k; i++)
	{
		int v, e;
		cin >> v >> e;
		
		//초기설정
		graph.resize(v + 1);
		check.resize(v + 1);
		visited.resize(v + 1);
		isEven = true;

		//그래프 입력받기
		for (int i = 0; i < e; i++)
		{
			int start, end;
			cin >> start >> end;
			graph[start].push_back(end);
			graph[end].push_back(start);
		}

		//그래프 전체 순회(DFS)
		for (int i = 1; i <= v; i++)
		{
			if (isEven)
			{
				DFS(i);
			}
			else
			{
				break;
			}
		}

		if (isEven)
		{
			cout << "YES" << "\n";
		}
		else
		{
			cout << "NO" << "\n";
		}

		//다시 기본값으로 초기화
		for (int i = 0; i <= v; i++)
		{
			graph[i].clear();
			visited[i] = false;
			check[i] = 0;
		}
	}
}


void DFS(int node)
{
	//방문처리
	visited[node] = true;

	//연결되어있는 노드탐색
	for (int i : graph[node])
	{
		//방문하지 않았다면
		if (!visited[i])
		{
			//다른 집합에 추가
			check[i] = (check[node] + 1) % 2;
			DFS(i);
		}
		//방문했고 만약 같은 집합이라면 사이클 발생
		else if (check[node] == check[i]) isEven = false;
	}
}