언제나 처음처럼

[문제 링크]

 먼저 입력으로 주어지는 건설 순서대로 그래프를 만든다. 필자는 역순으로 탐색할 계획이었기 때문에 X, Y 를 입력받았으면 Y정점에서 X정점으로 가는 간선을 연결하였다.

 그래프를 연결했으면 승리를 위한 건물을 시작정점으로 하는 깊이 우선 탐색을 수행하는데, 현재 정점의 건물까지 짓는데 걸리는 시간은 (현재 정점에서 건물을 짓는 시간 + 현재 정점에서 갈 수 있는 정점의 건물을 짓는데 걸리는 시간들 중 가장 큰 값) 이므로 이를 그대로 구현해주면 된다.

 추가로 이미 계산한 정점을 다시 호출하는 경우가 많으면 시간복잡도가 커지게 되므로 동적 계획법의 메모이제이션 기법을 통해 한번 계산한 정점의 최소 시간을 저장하여 중복되는 연산을 최소화해야 한다.

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

int N, K;
vector<int> adj[1001];
vector<int> weight(1001);
int memo[1001];

int dfs(int start) {
	int& ret = memo[start];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 0; i < adj[start].size(); i++) {
		int next = adj[start][i];
		ret = max(ret, dfs(next));
	}
	ret += weight[start];

	return ret;
}

int main(void) {
	int tc;
	cin >> tc;

	while (tc--) {
		memset(memo, -1, sizeof(memo));

		for (int i = 0; i < 1001; i++)
			adj[i].clear();

		cin >> N >> K;

		for (int i = 1; i <= N; i++)
			cin >> weight[i];

		for (int i = 0; i < K; i++) {
			int a, b;
			cin >> a >> b;
			adj[b].push_back(a);
		}

		int W;
		cin >> W;
		
		cout << dfs(W) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 166 day

[문제 링크]

입력으로 주어지는 순열과 1, 2, 3, ... N 순열은 서로 1:1 대응이라는 것을 알 수 있다.

따라서 입력받는 순서대로 1부터 N까지 정점을 연결한 다음, 모든 정점을 방문할 때 까지 dfs를 수행한 횟수를 출력하면 원하는 결과를 얻을 수 있다.

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

vector<int> adj(1001); // 1:1 그래프
vector<bool> visited(1001);

void dfs(int here) {
	visited[here] = true;
	int there = adj[here];
	if (!visited[there]) dfs(there);
}

int main(void) {
	int tc;
	cin >> tc;

	while (tc--) {
		int N;
		cin >> N;
		visited = vector<bool>(N + 1, false);

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

		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				cnt++;
				dfs(i);
			}
		}

		cout << cnt << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 165 day

[문제 링크]

 문제를 해결하기 위해 4가지 과정을 반복하였다.

1) iceMelt() 함수를 통해 빙산 주변에 있는 물의 수만큼 빙산을 녹인다.

2) 빙산이 2개 이상으로 나뉘어져 있는지 확인하기 위해 isSeparate() 함수를 정의하고, dfs() 를 통해 한 덩어리에 속한 빙산을 방문한다.

3)  만약 dfs()를 수행할 빙산이 없다면 모두 녹았다는 의미로 2를 반환한다.

4) dfs()를 수행했는데 아직 방문하지 않은 빙산이 있다면 분리되었다는 의미인 1을 반환하고, 모두 방문했다면 2개 이상으로 분리되지 않았다는 의미인 0을 반환한다.

isSeparate() 이 0을 반환했다면 위 과정을 다시 수행하고, 1을 반환했다면 누적한 시간을 출력, 2를 반환했다면 0을 출력한다.

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

struct Pos {
	int y;
	int x;
};

int N, M;
int board[300][300];
bool visited[300][300];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

void dfs(Pos here) {
	visited[here.y][here.x] = true;

	for (int i = 0; i < 4; i++) {
		int ny = here.y + dy[i];
		int nx = here.x + dx[i];
		if (ny >= 0 && ny < N && nx >= 0 && nx < M)
			if (!visited[ny][nx] && board[ny][nx] != 0)
				dfs({ ny, nx });
	}
}

int isSeparate() {
	memset(visited, false, sizeof(visited));

	bool check = false;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (board[i][j] != 0 && !visited[i][j]) {
				if (!check) {
					dfs({ i, j });
					check = true;
				}
				else 
					return 1;
			}

	if (!check) 
		return 2;
	else 
		return 0;
}

void iceMelt() {
	int temp[300][300];
	memcpy(temp, board, sizeof(board));

	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++) {
			if (temp[i][j] != 0) {
				int water = 0;
				for (int k = 0; k < 4; k++) {
					int ny = i + dy[k];
					int nx = j + dx[k];
					if (ny >= 0 && ny < N && nx >= 0 && nx < M)
						if (temp[ny][nx] == 0) water++;
				}
				board[i][j] -= water;
				if (board[i][j] < 0) board[i][j] = 0;
			}
		}
}

int solution() {
	int years = 0;
	int separate = isSeparate();

	while (separate == 0) {
		years++;
		iceMelt();
		separate = isSeparate();
	}

	if (separate == 1)
		return years;
	else
		return 0;
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> board[i][j];

	cout << solution() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 165 day

[문제 링크]

현재 좌표에서 동서남북 방향을 깊이 우선 탐색 함으로써 한 단지에 속하는 좌표를 방문하고 집의 개수를 저장하였다.

그리고 한번 깊이 우선 탐색을 했는데 방문하지 않은 좌표가 존재한다면 또다른 단지가 존재하는 것이므로 그 좌표를 시작으로 다시 깊이 우선 탐색 하는 것을 반복하도록 구현하였다.

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

int N;
vector<string> board(25);
bool visited[25][25];

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

struct Pos 
{
	int y;
	int x;
};

int dfs(Pos here)
{
	int ret = 1;

	for (int i = 0; i < 4; i++)
	{
		int ny = here.y + dy[i];
		int nx = here.x + dx[i];

		if (ny >= 0 && ny < N && nx >= 0 && nx < N)
			if (!visited[ny][nx] && board[ny][nx] == '1')
			{
				visited[ny][nx] = true;
				ret += dfs({ ny, nx });
			}
	}

	return ret;
}

int main(void) 
{
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> board[i];

	vector<int> result;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			if (!visited[i][j] && board[i][j] == '1')
			{
				visited[i][j] = true;
				Pos start = { i,j };
				result.push_back(dfs(start));
			}

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

	cout << result.size() << endl;
	
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 163 day