백준 17811 (원판 돌리기)

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

17822번: 원판 돌리기

해당 문제는 지문에 조건에 맞게 구현만 하면 되는 문제이다. 주의사항은 다음과 같다.

1. 인접한 요소를 찾을 때 인접한 Y축 (세로) 의 값을 비교할 경우 -1 or n 과 같아지는 경우 비교를 하지 않게 예외처리

2. 인접한 요소를 찾을 때 인접한 X축 (가로) 의 값을 비교할 경우 기준 X가 0 or m 과 같은 경우라면 X가 0일때는 기준 X축 배열의 가장 끝에 해당하는 요소와 비교를 수행하며 X가 m과 같은 경우에는 배열의 가장 첫 요소와 비교를 하여야 한다.

3. 만약 인접한 요소가 하나도 없을경우 평균을 구하여 평균과 배열의 값을 비교하며 ++ or -- 를 해주게 되는데 여기서 평균 값은 실수자료형으로 구해야한다.

 

풀이 :

Map을 주어진 명령에 맞게 회전시키는 함수와, 배열의 모든 요소를 탐색하며 요소의 값이 0보다 클 경우 해당 요소와 인접한 경우의 모든 요소를 찾아서 0으로 바꾸어 준다. 이때 모든 요소를 찾을 때에는 BFS를 통하여 구현하였다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node{
	int mapNum, dir, moveCnt;
};
struct Nodes{
	int y, x;
};

Node nodeList[50];
int checkY[4] = { 0, 0, -1, 1 };
int checkX[4] = { -1, 1, 0, 0, };
int n, m, t;
int map[50][50];

void spinMap(Node node){
	// mapNum의 배수의 원판을 dir 방향으로 moveCnt 칸 만큼 민다
	int i = 0;
	int dir = node.dir;
	int mCnt = node.moveCnt;

	while (i < mCnt){
		++i;
		if (node.dir == 0){
			// 시계
			for (int y = node.mapNum; y <= n; y += node.mapNum){
				int tmp = map[y - 1][m - 1];
				for (int x = m - 1; x >= 1; --x){
					map[y - 1][x] = map[y - 1][x - 1];
				}
				map[y - 1][0] = tmp;
			}
		}

		else{
			// 반 시계
			for (int y = node.mapNum; y <= n; y += node.mapNum){
				// 배수일 경우 밀기
				int tmp = map[y - 1][0];
				for (int x = 0; x < m - 1; ++x){
					map[y - 1][x] = map[y - 1][x + 1];
				}
				map[y - 1][m - 1] = tmp;
			}
		}
	}
}

// 배열의 요소 중 인접한 모든 값을 찾는 함수 
bool bfs(int y, int x, int num){
	int visit[50][50] = { 0 };
	queue<Nodes> qu;

	int flag = 0;
	visit[y][x] = 1;

	qu.push({y, x});
	while (!qu.empty()){
		Nodes now = qu.front();
		for (int i = 0; i < 4; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];
			// 기준 X 축이 0 일경우 해당 배열의 X 축 중 가장 마지막과 비교
			if (now.x == 0 && i == 0) dx = m - 1;
			// 기준 X 축이 해당 배열의 가장 마지막일 경우 해당 배열의 가장 첫 요소와 비교
			if (now.x == m - 1 && i == 1) dx = 0;
			if (dy < 0 || dx < 0 || dy >= n || dx >= m) continue;
			if (visit[dy][dx] == 1) continue;
			if (map[dy][dx] == num){
				visit[dy][dx] = 1;
				map[dy][dx] = 0;
				qu.push({ dy, dx });
				flag = 1;
			}
		}
		qu.pop();
	}
	if (flag == 1) {
		map[y][x] = 0;
		return true;
	}
	else{
		return false;
	}


}

// 회전 시킨 뒤 0보다 큰 배열의 모든 요소를 가지고 BFS 수행 
void checkList(){
	int flag = 0;
	int sum = 0, sumCnt = 0;
	double to = 0;
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j){
			if (map[i][j] <= 0) continue;
			// 만약 BFS가 수행 되었을 때 즉 인접하게 겹치는 수가 있을 경우 flag = 1;
			if (bfs(i, j, map[i][j]) == true) flag = 1;
		}
	}

	// 배열의 요소중 아무것도 겹치는게 없을 경우 
	if (flag == 0){
		for (int i = 0; i < n; ++i){
			for (int j = 0; j < m; ++j){
				if (map[i][j] > 0) {
					++sumCnt;
					sum += map[i][j];
				}
			}
		}
		// 실수형으로 평균을 구한다.
		to = (double(sum) / double(sumCnt));

		for (int i = 0; i < n; ++i){
			for (int j = 0; j < m; ++j){
				if (map[i][j] > 0){
					if (map[i][j] > to) map[i][j]--;
					else if (map[i][j] < to) map[i][j]++;
				}
			}
		}
	}

}


int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> m >> t;

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j){
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < t; ++i){
		int mapNum, dir, moveCnt;
		cin >> mapNum >> dir >> moveCnt;
		nodeList[i] = { mapNum, dir, moveCnt };
	}

	for (int i = 0; i < t; ++i){
		spinMap(nodeList[i]);
		checkList();
	}
	int sum = 0;

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j){
			if (map[i][j] > 0) sum += map[i][j];
		}
	}
	printf("%d", sum);

}