[백준/BOJ] 백준 21922번 : 학부 연구생 민상

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

21922번: 학부 연구생 민상

 

각 에어컨의 위치부터 4방향으로 바람이 나가면서 바람이 이동하는 위치들을 체크했다. 바람이 이동하면서, 같은 위치라도 어떤 방향으로 들어왔는지에 따라 다음에 이동하는 위치가 다를 수 있으므로, 각 위치에 어떤 방향으로 들어왔는지도 확인했다.

 

코드

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

int n, m;
int board[2005][2005];
int check[2005][2005]; //에어컨 바람의 영향이 있는 자리 체크
int visited[2005][2005][4]; //해당 위치에 바람이 어떤 방향으로 들어온적 있는지 체크
vector<pair<int, int>> starts;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void dfs(pair<int, int> here, int dir) {
	visited[here.first][here.second][dir] = 1;
	check[here.first][here.second] = 1;

	int next_dir = dir;

	//물건인 경우 방향 전환

	if (board[here.first][here.second] == 1) {
		if (dir == 0) {
			next_dir = 2;
		}

		if (dir == 2) {
			next_dir = 0;
		}
	}

	else if (board[here.first][here.second] == 2) {
		if (dir == 1) {
			next_dir = 3;
		}

		if (dir == 3) {
			next_dir = 1;
		}
	}

	else if (board[here.first][here.second] == 3) {
		if (dir == 0) {
			next_dir = 3;
		}
		if (dir == 1) {
			next_dir = 2;
		}
		if (dir == 2) {
			next_dir = 1;
		}
		if (dir == 3) {
			next_dir = 0;
		}
	}

	else if (board[here.first][here.second] == 4) {
		if (dir == 0) {
			next_dir = 1;
		}
		if (dir == 1) {
			next_dir = 0;
		}
		if (dir == 2) {
			next_dir = 3;
		}
		if (dir == 3) {
			next_dir = 2;
		}
	}

	pair<int, int> there = make_pair(here.first + dxdy[next_dir][0], here.second + dxdy[next_dir][1]);

	there = make_pair(here.first + dxdy[next_dir][0], here.second + dxdy[next_dir][1]);
	if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && visited[there.first][there.second][next_dir] == 0) {
		dfs(there, next_dir);
	}

}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int input;
			cin >> input;

			board[i][j] = input;

			if (input == 9) {
				starts.push_back(make_pair(i, j));
			}
		}
	}

	for (int i = 0; i < starts.size(); i++) {
		pair<int, int> start = starts[i];
		check[start.first][start.second] = 1;
		for (int dir = 0; dir < 4; dir++) {
			pair<int, int> there = make_pair(start.first + dxdy[dir][0], start.second + dxdy[dir][1]);

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && visited[there.first][there.second][dir] == 0) {
				dfs(there, dir);
			}
		}
	}

	int result = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (check[i][j] == 1) {
				result++;
			}
		}
	}

	cout << result;

	return 0;
}