취미로 코딩하기

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

이번에 볼 문제는 백준 6031번 문제인 Feeding Time이다.
문제는 아래 링크를 확인하자.

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

격자판에서 소가 상하좌우와 인접한 대각선 총 8방향으로 움직일 수 있을 때 각 풀이 있는 칸을 노드로, 이동할 수 있는 칸끼리 에지로 연결된 그래프에서 connected component의 크기의 최댓값을 구하는 문제이다.

단순히 각 connected component의 크기만을 구한다면 어떤 그래프탐색 알고리즘을 사용해도 상관없다. 글쓴이는 bfs를 이용하여 구현하였다.

아직 방문하지 않은 칸과, 바위가 있어 방문할 수 없는 칸을 헷갈리지 않게 주의하며 구현하자.

아래의 코드와 같이 dr 배열과 dc 배열을 만들어 8방향의 움직임을 편하게 구현할 수 있다.

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

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

int R, C;
string board[750];
bool visited[750][750];
int dr[8] = { 1,1,1,0,-1,-1,-1,0 };
int dc[8] = { 1,0,-1,-1,-1,0,1,1 };

int bfs(int sR, int sC) {
	int ret = 1;
	visited[sR][sC] = 1;
	queue<pair<int, int>> que;
	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) continue;
			if (board[rr][cc] == '*' || visited[rr][cc]) continue;
			visited[rr][cc] = 1, ret++;
			que.push(make_pair(rr, cc));
		}
	}

	return ret;
}

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

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

	int ans = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == '*' || visited[r][c]) continue;
			ans = max(ans, bfs(r, c));
		}
	}

	cout << ans;
}