[코드트리/C++] 캣타워 돌리기 (Simulation)

문제

https://www.codetree.ai/problems/rotate-cat-tower/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

구상

* 문제에서 주어지는 캣타워의 모습은 위에서 본 모습이 아닌 옆에서 본 모습이다!!

 

문제 자체만 보면 그냥 캣타워 돌리고 구조물이나 고양이 위로 고양이를 떨어뜨리면 되는, 그리 어려운 문제는 아닌데, 떨어뜨릴 때 다양한 경우의 수를 고려해야했다. 반시계방향이나 시계방향으로 돌리는 로직은 조금 까다로웠지만, 그래도 인덱스만 잘 고려하면 쉽게 구현할 수 있었다. 

if (dir == 1) { // 시계방향
    // 캣타워 돌리기
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            new_tower[j][rows - 1 - i] = tower[i][j];
        }
    }
}
else { // 반시계방향
    // 캣타워 돌리기
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            new_tower[cols - 1 - j][i] = tower[i][j];
        }
    }
}

 

고양이를 낙하시키는 방법은 여러가지가 있겠지만, 나는 열의 가장 아래(밑바닥)부터 고려하며 고양이가 떨어질 수 있는 spot을 갱신해주었다. 우선, 고양이가 있어야 할 위치부터 생각해보자.

 

고양이 아래에 빈칸이 있으면 안된다. = 고양이 아래에는 고양이 혹은 캣타워가 있어야 한다. 

=> 고양이를 만났을 때 spot으로 떨어뜨릴 수 있는지 없는지를 확인하자.

1. 내 로직에서는 sopt이 무조건 공란이 아닐 수도 있기에 sopt이 공란이라면 떨어드린다는 조건을 걸어 고양이를 spot으로 떨어뜨리자. 고양이가 한칸 이상의 공란을 거쳐 떨어졌다면 고양이가 떨어진 spot 위는 빈공간이다. spot = sopt -1로 갱신하자.

2. 만일 고양이가 떨어질 수 없는 안정적인 위치에 있다면, 고양이 위로 sopt을 갱신하자. 고양이 바로 위가 공란이 아닐 수도 있지만, 고양이 위로 고양이가 떨어질 수 있기 때문이다. 

 

구조물을 만났을 때에도 2번과 같이 구조물 위로 spot을 갱신시켜 spot이 공란이라면 고양이가 그곳으로 떨어질 수 있게 하였다. 

 

공란을 만났다면 spot을 그냥 유지시켜주면 되기에 아무것도 안해주었다. 

// 열 하나씩 보면서 고양이 낙하시키기
for (int i = 0; i < rows; i++) {
	int spot = cols-1;
	for (int j = cols - 1; j >= 0; j--) {
		if (new_tower[j][i] == 1 && j < spot && new_tower[spot][i] == 0) { // 고양이
			new_tower[j][i] = 0; new_tower[spot][i] = 1;
			spot = spot - 1;
		}
		else if (new_tower[j][i] == 1) {
			if (j - 1 >= 0) spot = j - 1;
		}

		else if (new_tower[j][i] == 2) { // 구조물 -> 아예 갱신
			if (j - 1 >= 0) spot = j - 1;
		}
		else if (new_tower[j][i] == 0) { // 빈칸 -> spot 과거의 것으로 유지

		}
	}
}

 

다음 회진을 위해 캣타워를 돌리고 고양이 떨어뜨릴 때마다 배열을 갱신해주었고, 열과 행의 크기도 갱신해주었다.

*배열이 n*n이라는 보장이 없었음

tower = new_tower;

if (rows == n) {
    rows = m; cols = n;
}
else if (rows == m) {
    rows = n; cols = m;
}

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define endl '\n'
using namespace std;
/*
캣타워 돌리기
https://www.codetree.ai/problems/rotate-cat-tower/description
*/

int n; int m; int q;
vector<vector<int>> tower(101, vector<int>(101));
int rows; int cols;

void SOLUTION() {
	
}
 
int main() {
	// 입력
	cin >> n >> m; // 캣타워 세로 길이, 가로길이
	cols = m; rows = n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tower[i][j];
		}
	}

	cin >> q; // 연산의 개수
	for (int i = 0; i < q; i++) { // 1이면 시계방향, -1이면 반시계 방향
		vector<vector<int>> new_tower(101, vector<int>(101));

		int dir;
		cin >> dir;
		if (dir == 1) { // 시계방향
			// 캣타워 돌리기
			for (int i = 0; i < rows; i++) {
				for (int j = 0; j < cols; j++) {
					new_tower[j][rows - 1 - i] = tower[i][j];
				}
			}
		}
		else { // 반시계방향
			// 캣타워 돌리기
			for (int i = 0; i < rows; i++) {
				for (int j = 0; j < cols; j++) {
					new_tower[cols - 1 - j][i] = tower[i][j];
				}
			}
		}
		// 디버깅
		cout << "회전 후" << endl;
		for (int i = 0; i < cols; i++) {
			for (int j = 0; j < rows; j++) {
				cout << new_tower[i][j] << " ";
			}
			cout << endl;
		}

		// 열 하나씩 보면서 고양이 낙하시키기
		for (int i = 0; i < rows; i++) {
			int spot = cols-1;
			for (int j = cols - 1; j >= 0; j--) {
				if (new_tower[j][i] == 1 && j < spot && new_tower[spot][i] == 0) { // 고양이
					new_tower[j][i] = 0; new_tower[spot][i] = 1;
					spot = spot - 1;
				}
				else if (new_tower[j][i] == 1) {
					if (j - 1 >= 0) spot = j - 1;
				}

				else if (new_tower[j][i] == 2) { // 구조물 -> 아예 갱신
					if (j - 1 >= 0) spot = j - 1;
				}
				else if (new_tower[j][i] == 0) { // 빈칸 -> spot 과거의 것으로 유지

				}
			}
		}
		// 디버깅
		cout << "낙하 후" << endl;
		for (int i = 0; i < cols; i++) {
			for (int j = 0; j < rows; j++) {
				cout << new_tower[i][j] << " ";
			}
			cout << endl;
		}

		tower = new_tower;

		if (rows == n) {
			rows = m; cols = n;
		}
		else if (rows == m) {
			rows = n; cols = m;
		}

	}

	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			cout << tower[i][j] << " ";
		}
		cout << endl;
	}
	

	return 0;
}