취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15240번 문제인 Paint bucket이다.
문제는 아래 링크를 확인하자.

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

주어진 좌표와 같은 색으로 연결된 영역을 주어진 색으로 채우는 문제이다.

DFS나 BFS등으로 flood fill을 구현해 주어진 좌표와 같은 색을 가진 영역을 채워나가자.

단, 각 좌표의 색이 무엇인지를 지표로 탐색 했던 픽셀인지를 판단하는 경우 한 영역을 원래 색과 같은 색으로 채워나갈 때 시간초과가 발생할 수 있으니 유의하자.

아래는 제출한 소스코드이다.

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

int R, C;
int sR, sC, fillcolor;
string s[1000];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs() {
	char fclr = fillcolor + '0';
	char cclr = s[sR][sC];
	assert(fclr != cclr);

	queue<pair<int, int>> que;
	que.push(make_pair(sR, sC));
	s[sR][sC] = fclr;
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second;
		que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (s[rr][cc] != cclr) continue;
			s[rr][cc] = fclr;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	cin >> R >> C;
	for (int r = 0; r < R; r++)cin >> s[r];

	cin >> sR >> sC >> fillcolor;

	bfs();

	for (int r = 0; r < R; r++) cout << s[r] << '\n';
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15241번 문제인 Counting paths이다.
문제는 아래 링크를 확인하자.

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

격자칸의 좌상단 칸에서 우하단 칸까지 이동하는 경로의 수를 세는 문제이다.

dp[r][c]를 좌상단 칸에서 r행 c열 칸까지 이동하는 경로의 수로 정의할 때 해당 위치가 'X'가 아니라면 dp[r][c] = dp[r-1][c] + dp[r][c-1]이 성립한다. 해당 위치가 'X'라면 값은 0이다.

아래는 제출한 소스코드이다.

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

int R, C;
string s[200];
int arr[201][201];

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> s[r];

	arr[1][1] = 1;
	s[0][0] = 'X';
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (s[r - 1][c - 1] == 'X') continue;
			arr[r][c] = arr[r - 1][c] + arr[r][c - 1];
			if (arr[r][c] > 1000000006) arr[r][c] -= 1000000007;
		}
	}

	cout << arr[R][C];
}