[백준]3055_탈출

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

Solved

매 분마다 고슴도치와 물은 비어있는 칸으로 이동할 수 있다 -> bfs
1. 초기화

• int r = 지도의 높이(배열의 raw의 수)
• int c = 지도의 넓이(배열의 column의 수)
• 이차원 배열 board, visit에 티떺숲 지형값 저장

#define rock -100000
int r, c;
char board[50][50];
int visit[50][50]; //0: empty, -100000: 돌, -1: 물
int direction[4][2] = { {0,1}, {0,-1},{1,0},{-1,0} };

2. bfs
   물의 이동(visit에 물이 차오를 예정이라 표시)
   → 고슴도치의 이동(물이 차오를 예정인 곳 피함)
   → visit에 '물이 차오를 예정이라 표시한 곳'을 '물이 차오른 곳'이라 표시

bool inRange(int x, int y) {
	return 0 <= x && x < r && 0 <= y && y < c;
}
void move_water() {
	// '*'은 이미 물이 범람한 자리
	// '@' 곧 물이 범람할 자리
	for (int i = 0; i < r; i++) {
		for (int j = 0; j< c; j++) {
			if (board[i][j] != '*') continue;
			for (int k = 0; k < 4; k++) {
				int nx = i + direction[k][0];
				int ny = j + direction[k][1];
				if (!inRange(nx, ny)) continue;
				if (board[nx][ny] == '.' || board[nx][ny] == 'S')
					board[nx][ny] = '@';
			}
		}
	}
}
int solution() {
	bool flag = false;
	int answer = -1;
	queue<tuple<int, int, int>> q; // x,y,cnt
	q.push(make_tuple(start.first,start.second,0));
	visit[start.first][start.second] = true;
	while (!q.empty()) {
		bool waterFlag = false;
		int x, y, curTime;
		tie(x, y, curTime) = q.front();
		if (curTime > answer) waterFlag = true;
		answer = curTime;
		q.pop();
		if (board[x][y] == 'D') {
			flag = true;
			break;
		}
		//물의 이동
		if(waterFlag) move_water();
		//고슴도치 이동
		for (int i = 0; i < 4; i++) {
			int nx = x + direction[i][0];
			int ny = y + direction[i][1];
			if (inRange(nx, ny) && (board[nx][ny] == '.' || board[nx][ny] == 'D') && !visit[nx][ny]) {
				visit[nx][ny] = true;
				q.push(make_tuple(nx, ny, answer+1));
			}
		}
		//@체크한 곳을 *로 바꿔주기
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (board[i][j] == '@') board[i][j] = '*';
			}
		}
	}
	return flag == true ? answer : -1;
}

3. 결과 출력

	int answer = solution();
	if (answer == -1) cout << "KAKTUS\n";
	else cout << answer << '\n';