[백준] 마법사 상어와 비바라기(21610 /C++)

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

21610번: 마법사 상어와 비바라기

코드 설명

이번 상반기 s사 기출문제이다... 분명 다풀었다고 생각했는데 자꾸 오류가나서 디버깅만 한시간했다...(함수형으로짜야 디버깅이 빠르다는걸 또 느꼈다...)

시험때 이러면 멘탈나가서 찾지도못할듯 -> 연산자 우선순위 생각!! 

 

우선 map이 전부 이어져 있다는 말은 결국 cycle처럼 0,1,2,3,4 가 있을때 5 는 0 이되고 -1은 4가 된다.

 

Move() 를통해 다음과 같이 cycle을 고려해주었다.

clouds[i].y += (dy[dir] * dis);
clouds[i].y %= N;

음수일 경우를 대비하여 각각 if (clouds[i].y < 0) clouds[i].y=(clouds[i].y + N) % N; 로 한번 더해준후 다시 나눠주는 tip!

 

그외 조심해야할 사항은 문제 똑바로 읽기! + visited배열과 같이 매번 가져다 쓰는거 초기화 잘해주기 !

 

코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int dx[] = { -1,-1,0,1,1,1,0,-1 };
int dy[] = { 0,-1,-1,-1,0,1,1,1 };
int map[51][51];
bool visited[51][51];
int N, M;
int dir, dis;

struct cloud { // 구름좌표
	int y;
	int x;
};
vector<cloud> clouds;
void Move(int dir, int dis) {

	for (int i = 0; i < clouds.size(); i++) {
		clouds[i].y += (dy[dir] * dis);
		clouds[i].y %= N;
		if (clouds[i].y < 0) clouds[i].y=(clouds[i].y + N) % N;
		clouds[i].x += (dx[dir] * dis);
		clouds[i].x %= N;
		if (clouds[i].x < 0) clouds[i].x=(clouds[i].x + N) % N;

	}

}
void Rain() {
	for (int i = 0; i < clouds.size(); i++) {
		map[clouds[i].y][clouds[i].x]++;
		
	}


}
void bfs() {
	queue<pair<int, int>> q;
	for (int i = 0; i < clouds.size(); i++) {
		q.push({ clouds[i].y,clouds[i].x });
		
	}
	
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		int cnt = 0;
		for (int i = 1; i < 8; i+=2) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (map[ny][nx]!=0) {
				cnt++;
				
			}


		}
		map[y][x] += cnt;


	}

}
void check() {
	for (int y = 0; y < N; y++) {

		for (int x = 0; x < N; x++) {
			if (!visited[y][x] && map[y][x]>=2) {
				clouds.push_back({ y,x });
				map[y][x] -= 2;
			}

		}
	}



}
int main() {
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
		}
	}
	//처음구름
	clouds.push_back({ N - 1,0 });
	clouds.push_back({ N - 2,0 });
	clouds.push_back({ N - 1,1 });
	clouds.push_back({ N - 2,1 });

	//구름 이동 입력 및 이동
	for (int i = 0; i < M; i++) {
		cin >> dir >> dis;
		dir--;
		
		//1.이동
		Move(dir, dis); 
		//2.비뿌리기(+1)
		Rain();
		//3.물복사버그 마법
		bfs();
		memset(visited, false, sizeof(visited));
		for (int i = 0; i < clouds.size(); i++) {
			visited[clouds[i].y][clouds[i].x] = true;
		}
		//3.구름 사라지기
		clouds.clear();
		//4.물의양이 2이상인 모든칸에 구름이 생기며 물의양-2 (기존 구름 제외)
		check();
		memset(visited, false, sizeof(visited));
		
	}

	int answer = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			answer += map[y][x];
		}
	}

	cout << answer;
	return 0;
}