언제나 처음처럼

[문제 링크]

전체 그래프를 탐색하면서 아직 방문하지 않은 섬을 만나면 해당 섬의 좌표를 시작으로 하는 bfs를 수행하여 하나로 연결된 섬을 찾는다.

모든 좌표를 탐색했을 때 수행한 bfs 횟수가 곧 섬의 개수가 된다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int w, h;
bool adj[50][50];
bool visited[50][50];
int dy[8] = { 0,0,-1,-1,-1,1,1,1 };
int dx[8] = { 1,-1,0,1,-1,0,1,-1 };

struct Pos {
	int y;
	int x;
};

void bfs(int startY, int startX) {
	queue<Pos> q;
	q.push({ startY, startX });
	visited[startY][startX] = true;

	while (!q.empty()) {
		int hereY = q.front().y;
		int hereX = q.front().x;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if(nextY >= 0 && nextY < h && nextX >= 0 && nextX < w)
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					q.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
		}
	}
}

int getIslandCount() {
	int cnt = 0;

	for(int y=0; y<h; y++)
		for (int x = 0; x < w; x++) {
			if (adj[y][x] && !visited[y][x]) {
				cnt++;
				bfs(y, x);
			}
		}

	return cnt;
}

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

	while (true) {
		cin >> w >> h;
		if (w == 0 && h == 0)
			break;
		memset(adj, false, sizeof(adj));
		memset(visited, false, sizeof(visited));

		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				int n;
				cin >> n;
				adj[y][x] = n;
			}
		}
				
		cout << getIslandCount() << '\n';
	}

	return 0;
}

[문제 링크]

문제를 풀기 전에 연결 요소가 뭔지 알아야 할 필요가 있다.

연결 요소란? 그래프에서 하나로 연결된 정점들의 집합이라고 생각하면 된다.

그래프의 모든 정점을 방문할 때 까지 bfs나 dfs를 수행한 다음, 수행한 횟수가 곧 연결 요소의 갯수가 된다.

정점의 개수가 많고 양방향 그래프로 표현해야 하기 때문에 인접 행렬보단 인접 리스트로 그래프를 구현하는 것이 효율적이고 직관적이라고 생각한다.

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

int N, M;
vector<int> adj[1001];
bool visited[1001];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();

		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i];
			
			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
}

int getConnectedComponent() {
	int result = 0;

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			result++;
			bfs(i);
		}
	}

	return result;
}

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

	// 양방향 그래프로 구현할 것
	while(M--) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cout << getConnectedComponent() << endl;

	return 0;
}

[문제 링크]

수빈이가  위치한 좌표를 시작으로 +1 하는 경우, -1 하는 경우, *2 하는 경우 도달하는 좌표를 큐에 담는 방식으로 bfs를 수행하면 정답을 얻을 수 있다.

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

bool visited[100001];
int N, K;

int bfs() {
	queue<pair<int, int>> q;
	q.push({N, 0});
	visited[N] = true;

	while (!q.empty()) {
		int here = q.front().first;
		int sec = q.front().second;
		q.pop();

		if (here == K) return sec;

		sec++;
		int next = here + 1;
		if (next <= 100000 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}
		
		next = here - 1;
		if (next >= 0 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}

		next = here * 2;
		if (next <= 100000 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}
	}

	// 이 행에 도달했다면 만나는건 불가능(가능성 0%)
	return -1;
}

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

	cout << bfs() << endl;
	
	return 0;
}

[문제 링크]

N,M의 최대값이 1000으로 꽤 큰편이기 때문에 그래프의 전체 탐색 횟수를 줄이기 위해 익은 토마토의 위치를 큐에 담아놓고 탐색하는 방법으로 구현하였다.

입력을 받을 때 안익은 토마토의 갯수를 카운팅하고 익은 토마토의 좌표를 큐에 담는다.

그 다음, 큐에 담긴 익은 토마토 좌표를 기준으로 동서남북을 확인하여 안익은 토마토를 찾아 해당 토마토를 익은 토마토로 바꾸고 큐에 담는다.

안익은 토마토의 갯수가 0이 되거나 새롭게 익은 토마토가 더이상 존재하지 않을 때까지 위 작업을 반복하면 된다.

안익은 토마토의 갯수가 0이 되었을때 반복한 횟수가 곧 최소 일수가 되며,

새롭게 익은 토마토가 더이상 존재하지 않을 때 안익은 토마토가 남아 있다면 토마토를 모두 익게 만드는 것은 불가능하다.

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

struct Pos {
	int y;
	int x;
};

// M: 가로, N: 세로
int M, N;
int adj[1000][1000];
int tomatoCnt;
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };
queue<Pos> ripeTomatoQueue;

int getRipeTomatoDays() {
	int result = 0;

	while (tomatoCnt > 0) {
		if (ripeTomatoQueue.empty())
			return -1;

		result++;
		int qSize = ripeTomatoQueue.size();
		while (qSize--) {
			Pos herePos = ripeTomatoQueue.front();
			ripeTomatoQueue.pop();

			for (int i = 0; i < 4; i++) {
				Pos nextPos = { herePos.y + dy[i], herePos.x + dx[i] };
				
				if(nextPos.y >= 0 && nextPos.y < N && nextPos.x >= 0 && nextPos.x < M)
					if (adj[nextPos.y][nextPos.x] == 0) {
						adj[nextPos.y][nextPos.x] = 1;
						tomatoCnt--;
						ripeTomatoQueue.push(nextPos);
					}
			}
		}
	}

	return result;
}

int main(void) {
	cin.tie(0);

	cin >> M >> N;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> adj[y][x];
			Pos pos = { y,x };

			if (adj[y][x] == 0)
				tomatoCnt++;
			else if (adj[y][x] == 1)
				ripeTomatoQueue.push(pos);
		}
	}

	cout << getRipeTomatoDays() << endl;

	return 0;
}

[문제 링크]

간단한 그래프 탐색 문제였다.

그래프를 탐색하면서 배추가 있는 땅을 시작으로 하는 bfs를 수행하고 인접해 있는 배추를 방문 표시한다.

모든 좌표를 탐색했을 때 bfs 호출 횟수가 지렁이의 마리 수가 된다.

#include <iostream>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;

// M: 가로길이(x), N: 세로길이(y), K: 배추가 심어진 개수
int M, N, K;
bool adj[50][50];
bool visited[50][50];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };

struct Pos {
	int y;
	int x;
};

void bfs(int startY, int startX) {
	queue<Pos> q;
	q.push({ startY, startX });
	visited[startY][startX] = true;

	while (!q.empty()) {
		int hereY = q.front().y;
		int hereX = q.front().x;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					q.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
			}
		}
	}
}

void dfsStack(int startY, int startX) {
	stack<Pos> stk;
	stk.push({ startY, startX });
	visited[startY][startX] = true;

	while (!stk.empty()) {
		int hereY = stk.top().y;
		int hereX = stk.top().x;
		stk.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					stk.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
		}
	}
}

void dfsRecursion(int startY, int startX) {
	visited[startY][startX] = true;

	for (int i = 0; i < 4; i++) {
		int nextY = startY + dy[i];
		int nextX = startX + dx[i];

		if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
			if (adj[nextY][nextX] && !visited[nextY][nextX]) {
				dfsRecursion(nextY, nextX);
			}
	}
}

int graphSearchAll() {
	int result = 0;

	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++) {
			if (adj[y][x] && !visited[y][x]) {
				result++;
				bfs(y, x);
				//dfsStack(y, x);
				//dfsRecursion(y, x);
			}
		}

	return result;
}

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

	while (tc--) {
		cin >> M >> N >> K;

		memset(adj, false, sizeof(adj));
		memset(visited, false, sizeof(visited));

		while (K--) {
			int x, y;
			cin >> x >> y;
			adj[y][x] = true;
		}

		cout << graphSearchAll() << endl;
	}

	return 0;
}

[문제 링크]

문제에서 요구하는 조건대로 구현해주면 되는 문제였다.

입력으로 주어지는 정수의 최솟값이 -50 이므로, 음수까지 메모이제이션 하기 위해 값에 50을 더해줬다.

또한 a, b, c 셋 중에 하나라도 20을 넘는 값이 있을 경우 w(20, 20, 20)으로 재귀 호출 하기 때문에, memo 배열의 최대 크기를 101이 아닌 71로 선언하여 공간 복잡도를 줄였다.

#include <iostream>
using namespace std;

const int INF = 987654321;
int memo[71][71][71];

int dp(int a, int b, int c) {
	if (a <= 0 || b <= 0 || c <= 0) return 1;
	else if (a > 20 || b > 20 || c > 20) return dp(20, 20, 20);

	int& ret = memo[a+50][b+50][c+50];
	if (ret != 0)
		return ret;

	if (a < b && b < c)
		return ret = dp(a, b, c - 1) + dp(a, b - 1, c - 1) - dp(a, b - 1, c);
	else
		return ret = dp(a - 1, b, c) + dp(a - 1, b - 1, c) + dp(a - 1, b, c - 1) - dp(a - 1, b - 1, c - 1);
}

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

	while (true) {
		int a, b, c;
		cin >> a >> b >> c;

		if (a == -1 && b == -1 && c == -1)
			break;
		else {
			cout << "w(" << a << ", " << b << ", " << c << ") = " << dp(a,b,c) << '\n';
		}
	}

	return 0;
}

[문제 링크]

M이 100,000으로 매우 크기 때문에 행을 입력 받을 때 미리 각 행의 누적합을 구해놓고 이를 참조하는 방식으로 구현하였다.

(2,2) ~ (3,4) 의 구간합을 구해보자면,

(2,2) ~ (2,4) 까지의 합 + (3,2) ~ (3,4) 까지의 합이 된다.

(2,2) ~ (2,4) 까지의 합은 미리 구해놨던 (2,1) ~ (2,4) 까지의 누적합에 (2,1) ~ (2,1) 까지의 누적합을 빼준 것과 같다는 것을 알 수 있다.

(3,2) ~ (3,4) 까지의 합도 마찬가지로 (3,1) ~ (3,4) 까지의 누적합에 (3,1) ~ (3,1) 까지의 누적합을 빼준 것과 같다.

#include <iostream>
using namespace std;

int memo[1025][1025];

int sum(int y1, int x1, int y2, int x2) {
	int result = 0;
	for (int y = y1; y <= y2; y++) {
		if (x1 == 1)
			result += memo[y][x2];
		else
			result += memo[y][x2] - memo[y][x1-1];
	}

	return result;
}

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

	int N, M;
	cin >> N >> M;

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			int num;
			cin >> num;

			if (x == 1)
				memo[y][x] = num;
			else
				memo[y][x] = memo[y][x - 1] + num;
		}
	}

	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;

		cout << sum(y1, x1, y2, x2) << '\n';
	}

	return 0;
}

[문제 링크]

간단한 DP 문제였다.

상근이가 N킬로그램을 배달하는 봉지의 최소 갯수를 점화식으로 표현하면 다음과 같다.

result = 1 + min(dp(N-3), dp(N-5))

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int INF = 987654321;
int memo[5001];

int dp(int N) {
	if (N == 0) return 0;
	else if (N < 0) return INF;

	int& ret = memo[N];
	if (ret != -1)
		return ret;
	ret = INF;

	return ret = min(ret, 1 + min(dp(N - 3), dp(N - 5)));
}

int main(void) {
	memset(memo, -1, sizeof(memo));

	int N;
	cin >> N;
	
	int result = dp(N);
	cout << (result == INF ? -1 : result) << endl;

	return 0;
}