[백준 21922] 학부 연구생 민상

재귀 돌려서 풀었다.

중간에 재귀 내 코드를 바꾼 부분은 이 두 부분 때문이다.

 

1. visited 했다고 못가는 것이 아니라는 거

 

처음에는 visited 했으면(에어컨바람이 한번 지나간 곳이면) 아예 더 이상 진행 못하게 했는데

만약 다른 방향으로 에어컨 바람이 진행되고 있었으면 visited 했던 곳도 또 갈 수 있다.

따라서 방문했다고 바로 return 해버리는 것은 옳지 않다.

 

2. 에어컨인 곳이면 return 해도 된다는거

 

1번만 바꾸고 냈는데 60%에서 시간초과가 떴다.

그래서 생각을 해보니 만약 에어컨이 있는 곳에 도달했으면 탐색하지 않아도 된다.

왜냐하면 에어컨이 있는 위치는 모든 방향으로 바람이 나가는 곳이기 때문에

내가 굳이 지금 특정 방향으로 진행을 안해줘도 해당 방향으로 진행이 될 곳이기 때문이다.

그래서 에어컨인 칸이면 종료되게 하였다 그랬는데 통과함.

 

3. enum 쓰다가 그냥 define으로 바꿨다

enum을 안써도 된다! 그냥 define 해주면 된다!!

 

 

visited는 2차원 bitset으로 해결했다

bitset의 count함수를 통해 한번에 visited한 칸의 갯수를 구할 수 있다

 

---

#include <iostream>
#include <vector>
#include <bitset>

#define SIZE 2001
#define LEFT 0
#define UP 1
#define RIGHT 2
#define DOWN 3

using namespace std;

int room[SIZE][SIZE];

vector<pair<int, int>> aircon;
bitset<SIZE> visited[SIZE];

int width, height;

// dir LEFT UP RIGHT DOWN
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int cnt = 0;

void solve(int y, int x, int curdir) {

	// 범위 넘어 서면
	if (y<1 || y>height || x<1 || x>width) return;

	// 세로 물체
	if (room[y][x] == 1) {
		if (curdir == LEFT || curdir == RIGHT) {
			visited[y][x] = 1;
			return;
		}
	}
	// 가로 물체
	else if (room[y][x] == 2) {
		if (curdir == UP || curdir == DOWN) {
			visited[y][x] = 1;
			return;
		}
	}
	//위 방향 대각선
	else if (room[y][x] == 3) {
		if (curdir == LEFT) { curdir = DOWN; }
		else if (curdir == UP) { curdir = RIGHT; }
		else if (curdir == RIGHT) { curdir = UP; }
		else if (curdir == DOWN) { curdir = LEFT; }
	}
	// 아래 방향 대각선
	else if (room[y][x] == 4) {
		if (curdir == LEFT) { curdir = UP; }
		else if (curdir == UP) { curdir = LEFT; }
		else if (curdir == RIGHT) { curdir = DOWN; }
		else if (curdir == DOWN) { curdir = RIGHT; }
	}

	visited[y][x] = 1; // 방문처리

	int nexty = y + dy[curdir];
	int nextx = x + dx[curdir];

	// 다음꺼가 에어컨이면 멈추기
	if (room[nexty][nextx] == 9) {
		visited[nexty][nextx] = 1;
		return;
	}

	solve(y + dy[curdir], x + dx[curdir], curdir);
	return;
}

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

	cin >> height >> width;
	for (int i = 1; i <= height; i++) {
		for (int k = 1; k <= width; k++) {
			cin >> room[i][k];
			if (room[i][k] == 9) {
				aircon.push_back(make_pair(i, k));
			}
		}
	}

	for (int i = 0; i < aircon.size(); i++) {
		int y = aircon[i].first;
		int x = aircon[i].second;
		solve(y, x, LEFT);
		solve(y, x, UP);
		solve(y, x, RIGHT);
		solve(y, x, DOWN);
	}

	for (int i = 1; i <= height; i++) cnt += visited[i].count();

	cout << cnt;
	return 0;
}