21922번: 학부 연구생 민상

2022.02.14

 

문제 출처:

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

 

문제 분석:

문제의 조건에 따라 구현해 내는 구현 문제인것 같다.

 

문제 해결:

에어컨을 기준으로 상하좌우로 바람을 보내 바람이 물건을 만났을때 그에 해당하는 방향으로

회전 시켜주는 것을 구현하는 문제

물건 1,2 같은경우는 튕겨나가서 반대방향으로 가는것은 어차피 겹치기때문에 구현하지 않아도 되고

에어컨을 만나는 경우에는 그 에어컨에서 바람이 나올것이기 때문에 정지 해줘도 된다.

 

핵심은 방문처리를 하는 부분에서 방향에 따라 다르게 3차원으로 칠해야 되는 것 같다.

 

내 소스코드:

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int INF = 987654321;

int arr[2002][2002];
int N, M;
vector<pii> aircon;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int check[2002][2002][4];
int dirOp[4] = {2, 3, 0, 1};

int converter(int cur, int dir)
{
	if (cur == 3)
	{
		if (dir == 0)
			return 1;
		else if (dir == 1)
			return 0;
		else if (dir == 2)
			return 3;
		else if (dir == 3)
			return 2;
	}
	else if (cur == 4)
	{
		if (dir == 0)
			return 3;
		else if (dir == 1)
			return 2;
		else if (dir == 2)
			return 1;
		else if (dir == 3)
			return 0;
	}
	return 0;
}

void bfs(int startY, int startX)
{
	for (int i = 0; i < 4; i++)
	{
		check[startY][startX][i] = 1;
	}
	queue<pair<pii, int>> q;
	for (int i = 0; i < 4; i++)
	{
		q.push({{startY, startX}, i});
	}

	while (!q.empty())
	{
		int startY = q.front().F.F;
		int startX = q.front().F.S;
		int dir = q.front().S;
		q.pop();

		int nY = startY + dy[dir];
		int nX = startX + dx[dir];

		if (nY < 0 || nX < 0 || nY >= N || nX >= M)
			continue;
		if (check[nY][nX][dir] == 1)
			continue;

		check[nY][nX][dir] = 1;

		if (arr[nY][nX] == 0)
			q.push({{nY, nX}, dir});
		else if (arr[nY][nX] == 1 || arr[nY][nX] == 2)
		{
			if (arr[nY][nX] == 1)
			{
				if (dir == 1 || dir == 3)
				{
					check[nY][nX][dir] = 1;
					continue;
				}
				else
					q.push({{nY, nX}, dir});
			}
			else if (arr[nY][nX] == 2)
			{
				if (dir == 0 || dir == 2)
				{
					check[nY][nX][dir] = 1;
					continue;
				}
				else
					q.push({{nY, nX}, dir});
			}
		}
		else
		{
			q.push({{nY, nX}, converter(arr[nY][nX], dir)});
		}
	}
}

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

	memset(check, 0, sizeof(check));

	cin >> N >> M;

	rep(i, N)
	{
		rep(j, M)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 9)
			{
				aircon.push_back({i, j});
			}
		}
	}

	for (int i = 0; i < aircon.size(); i++)
	{
		int airconY = aircon[i].F;
		int airconX = aircon[i].S;

		bfs(airconY, airconX);
	}

	int ans = 0;
	rep(i, N)
	{
		rep(j, M)
		{
			rep(k, 4)
			{
				if (check[i][j][k] == 1)
				{
					ans++;
					k = 4;
				}
			}
		}
	}

	cout << ans;

	return 0;
}

고찰: 

처음에 DFS로 짰을때 시간초과가 계속 났는데 원인을 알 수가 없어서

BFS로 고쳤더니 통과가 되었다.