취미로 코딩하기

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

이번에 볼 문제는 백준 4657번 문제인 Image Perimeters이다.
문제는 아래 링크를 확인하자.

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

클릭으로 표시된 8방향 기준 connected component의 둘레의 길이를 구하는 문제이다.

8방향 기준 connected component는 bfs등의 그래프 탐색을 통해, 그 둘레의 길이는 connected component를 구성하는 각 칸의 주변 'X'가 아닌 칸 수를 세어 합하는 것으로 구할 수 있다

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

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

int R, C, sR, sC;
string board[20];
int visited[20][20];

int dr[8] = { 1,-1,0,0,1,-1,-1,1 };
int dc[8] = { 0,0,1,-1,1,1,-1,-1 };

queue<pair<int, int>> que;

void solve() {
	int ans = 0;
	memset(visited, 0, sizeof(visited));
	for (int r = 0; r < R; r++) cin >> board[r];
	
	if (board[sR][sC] == 'X') {
		visited[sR][sC] = 1;
		que.push(make_pair(sR, sC));
	}

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C || visited[rr][cc] || board[rr][cc] == '.') continue;
			visited[rr][cc] = 1;
			que.push(make_pair(rr, cc));
		}
		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) ans++;
			else if (board[rr][cc] == '.') ans++;
		}
	}

	cout << ans << '\n';
}

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

	cin >> R >> C >> sR >> sC;
	while (R) {
		sR--, sC--;
		solve();
		cin >> R >> C >> sR >> sC;
	}
}