[구름] 단풍나무 C++

https://level.goorm.io/exam/167345/%EB%8B%A8%ED%92%8D%EB%82%98%EB%AC%B4/quiz/1

구름LEVEL

 

 

풀이

 

 

처음엔 단순하게 타일 하나하나 탐색하면서 인접타일의 값이 0이라면 현재 타일의 값을 -1 해봤는데

하루 단위에서 인접한 타일의 값이 1에서 0으로 바뀐 경우 해당 타일을 0으로 인식하여 값이 변동되는 문제 발생

 

-- 큐에 좌표값을 담아서 따로 한번에 값 변경하는 방식으로 해결

 

 

1. 모든 타일을 탐색

2. 0이 아닌 타일 발견 시, 해당 타일의 4방향으로 인접한 타일들의 값이 0이라면, 해당 타일의 x, y 좌표를 큐에 삽입

3. 큐에서 하나하나 꺼내면서 해당 타일의 값을 -1, 0보다 작아진다면 0으로

4. answer 변수 +1 (하루가 지남)

 

-- 반복

 

 

queue<pair<int, int>> inputSearch(vector<vector<int>> input, int n) {
	
    // input vector 값을 update하기 위한 좌표 정보를 담을 큐
	queue<pair<int, int>> q;
	int xdir[4] = { 0, 0, 1, -1 };	// 인접노드 탐색 x방향
	int ydir[4] = { 1, -1, 0, 0 };	// 인접노드 탐색 y방향

	// 모든 타일 하나하나 방문하며
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int curX = i;
			int curY = j;

			// 현재 타일이 0이 아니라면 (물들 수 있다면)
			if (input[curX][curY] != 0) {
				// 현재 타일과 인접한 4개의 타일 탐색
				for (int k = 0; k < 4; k++) {
					int nextX = curX + xdir[k];
					int nextY = curY + ydir[k];

					// 인접한 타일이 전체 범위 안이면서
					if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n) {
						// 인접한 타일의 값이 0이라면 q에 삽입
                        if (input[nextX][nextY] == 0) {
							q.push(make_pair(curX, curY));
						}
					}
				}
			}
		}

	}

	// 인접한 타일의 영향을 받아 물들어갈 타일의 좌표를 담은 큐를 return
	return q;
}


vector<vector<int>> inputUpdate(queue<pair<int, int>> q, vector<vector<int>> input) {

	// 큐 안의 좌표를 하나하나 꺼내면서 값을 -1
	while (!q.empty()) {

		int x = q.front().first;
		int y = q.front().second;

		q.pop();
		input[x][y] -= 1;

		if (input[x][y] < 0)
			input[x][y] = 0;
	}
	
    // 변경된 input vector를 return
	return input;
}


int main() {

	int n;		// x, y축 크기
	cin >> n;

	vector<vector<int>> input;		// input 값을 담을 vector 컨테이너

	int answer = 0;
    
    // 반복문으로 input vector에 문제 입력값 삽입
	for (int i = 0; i < n; i++) {
		vector<int> temp;
		for (int j = 0; j < n; j++) {
			int m;
			cin >> m;
			temp.push_back(m);
		}
		input.push_back(temp);
	}

	// while 한 번이 하루
	while (1) {

		queue<pair<int, int>> q = inputSearch(input, n);

		// q에 아무것도 담겨있지 않다면 >> 더이상 물들 단풍나무가 없다면 while 탈출
		if (q.empty())
			break;

		// q에 값이 있다면 하루가 지나고
		answer++;
        
        // input vector의 값을 변경 (물든 상태로)
		input = inputUpdate(q, input);

	}


	cout << answer << endl;

}