취미로 코딩하기

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

이번에 볼 문제는 백준 26076번 문제인 곰곰이의 식단 관리 2이다.
문제는 아래 링크를 확인하자.

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

곰곰이의 출발 위치의 아래와 오른쪽칸에 장애물을 설치하는 등의 방법으로 항상 곰곰이가 치킨을 향해 이동하는 것을 막을 수 있으므로 답은 항상 0, 1 또는 2 셋 중 하나이다.

곰곰이의 출발 위치에서 상하좌우 이동을 이용하여 치킨이 있는 칸까지 이동을 원래 할 수 없다면 0을 출력해주자.

한 칸만 놓아도 충분한 경우, 그 놓아야 할 칸의 인접한 여덟 칸 가운데 "장애물 칸이면서 그 장애물 위에서 여덟방향 이동만으로 윗변또는 오른쪽 변까지 도달할 수 있는 칸"과 "장애물 칸이면서 그 장애물 위에서 여덟방향 이동만으로 아랫변 쪼는 왼쪽 변까지 도달할 수 있는 칸"이 둘 다 존재해야 함을 알 수 있다. 이는 각 변에서부터 장애물 칸을 따라 여덟 방향으로 탐색하는 bfs를 통해 구해낼 수 있다.

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

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

int R, C;
int board[2000][2000];
int dr[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };
int dc[8] = { 1, 0, -1, -1, -1, 0, 1, 1 };

bool visited[2000][2000];
void bfs0() {
	visited[0][0] = 1;
	queue<pair<int, int>> que;
	que.push(make_pair(0, 0));

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

bool chk1[2000][2000];
void bfs1() {
	queue<pair<int, int>> que;
	for (int c = 1; c < C; c++) {
		chk1[0][c] = 1;
		if (board[0][c]) que.push(make_pair(0, c));
	}
	for (int r = R - 2; r > 0; r--) {
		chk1[r][C - 1] = 1;
		if (board[r][C - 1]) que.push(make_pair(r, C - 1));
	}

	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 || chk1[rr][cc]) continue;
			chk1[rr][cc] = 1;
			if (board[rr][cc] == 1) que.push(make_pair(rr, cc));
		}
	}
	chk1[0][0] = chk1[R - 1][C - 1] = 0;
}

bool chk2[2000][2000];
void bfs2() {
	queue<pair<int, int>> que;
	for (int r = 1; r < R; r++) {
		chk2[r][0] = 1;
		if (board[r][0]) que.push(make_pair(r, 0));
	}
	for (int c = 1; c < C - 1; c++) {
		chk2[R - 1][c] = 1;
		if (board[R - 1][c]) que.push(make_pair(R - 1, c));
	}

	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 || chk2[rr][cc]) continue;
			chk2[rr][cc] = 1;
			if (board[rr][cc] == 1) que.push(make_pair(rr, cc));
		}
	}
	chk2[0][0] = chk2[R - 1][C - 1] = 0;
}

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

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

	bfs0();
	if (visited[R - 1][C - 1] == 0) {
		cout << 0;
		return 0;
	}

	bfs1();
	bfs2();

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (chk1[r][c] && chk2[r][c]) {
				cout << 1;
				return 0;
			}
		}
	}

	cout << 2;
}