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

https://www.acmicpc.net/status?from_mine=1&problem_id=21610&user_id=mina3215

채점 현황

 

[문제 요약]

1. NXN 격자의 모든 칸에 물을 저장하는 바구니가 있다. (1,1) ~ (N,N)

2. 비바라기를 시전하면 (N,1),(N,2),(N-1,1),(N-2,2)에 비구름이 생성된다. 

3. 그 후 d 방향으로 s 만큼 M번의 명령을 받는다. 방향은 1~8   ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 

4. 명령을 행하는 순서는 다음과 같다.

 

[문제 풀이]

일단, 보자마자 구현문제라고 생각했다. 

그래서, 다음과 같은 로직으로 진행해야 한다고 생각

1) d, s 입력 

2) 구름이 있을 위치를 찾고 (d*s)를 더해준다. => vector<pair<int,int>> v

3) 경계선의 위치를 고려해서 구해주고 해당 위치에서 +1

=>

0보다 크면, (x+ dx[d]*s)%N

0보다 작으면 (x+dx[d]*s)+N (while)

3) 대각선을 보고 위치한 개수만큼 더해준다. => dgdy[], dgdx[]

4) 2이상인 칸과 그 전에 비가 온 칸은 따로 구분. => NXN의 새로운 2차원 배열 cnt!=cnt-1

 

#include<bits/stdc++.h>

using namespace std;

//1~8
int dy[] = {0,0,-1,-1,-1,0,1,1,1};
int dx[] = {0,-1,-1,0,1,1,1,0,-1};

int land[50][50];
int rained[50][50];

int N, M;

// 대각선 찾기
void findDg(vector<pair<int, int>> v) {
	int dgdy[] = {1,1,-1,-1};
	int dgdx[] = {1,-1,1,-1};

	for (auto i : v) {
		for (int j = 0; j < 4; j++) {
			int dgy = i.first + dgdy[j];
			int dgx = i.second + dgdx[j];
			//경계에 있거나 0이면 continue
			if (dgy<0 || dgx<0 || dgy>=N || dgx>=N) continue;
			if (land[dgy][dgx] == 0) continue;
			land[i.first][i.second] += 1;
		}
	}
}


// 비 내리는 구현
void rain(int cnt, int d, int s) {
	// 구름이 시작되는 칸을 담을 벡터
	vector<pair<int, int>> v;

	// 첫번째 시도는 무조건 우측 아래에서 시작한다.
	// 조건문으로 처리
	if (cnt == 1) {
		v.push_back({ N - 1,  0 });
		v.push_back({ N - 1, 1 });
		v.push_back({ N - 2, 0 });
		v.push_back({ N - 2, 1 });
	}else {
		// 첫번째가 아닐 경우, 2칸이상 이 전에 비가 온 칸이 아니면 그 칸은 시작 칸이 된다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (land[i][j] >= 2 && rained[i][j]!=cnt-1) {
					v.push_back({ i,j });
					land[i][j] -= 2;
				}
			}
		}
	}

	//이동할 거리 * 방향
	int ny = dy[d] * s;
	int nx = dx[d] * s;
	//벡터 안의 구름을 이동시킨다.
	for (auto &i : v) {
		i.first += ny;
		i.second += nx;
		//이동한 y 위치가 0 이하
		while(i.first < 0) i.first += N;
		i.first = i.first%N;
		//이동한 x 위치가 0 이하인 경우
		while(i.second < 0) i.second += N;
		i.second = i.second%N;
		//비를 내리고
		land[i.first][i.second] += 1;
		//비가 내렸음을 표기
		rained[i.first][i.second] = cnt;
	}

	// 대각선 찾기.-> 모든 칸에 비를 내린 후 해야함.
	findDg(v);

}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> land[i][j];
		}
	}
	int d, s;
	fill(&rained[0][0], &rained[0][0] + 50 * 50, 0);
	

	//명령 실행
	for (int t = 1; t <= M; t++) {
		cin >> d >> s;
		rain(t, d,s);
	}

	//마지막으로 2이상 찾아서 빼주는 부분.
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (land[i][j] >= 2 && rained[i][j] != M) {
				land[i][j] -= 2;
			}
		}
	}


	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ans += land[i][j];
		}
	}
	cout << ans;
}

 

[고찰]

놓친 부분

1.처음에는 단순히 위치가 - 일때, +N만 해줬었는데 디버깅을 통해서 이러면 안된다는걸 깨달았다...

while로 바꿔줬음.

2. 구현에 힘을 쏟다보니 문제에 적혀있는 내용을 하나씩 빼먹음... 아휴

3. vector<pair<int, int>> v  for(auto i: v)로 돌리는 경우, i.first, i.second에 얕은 복사가 일어난다고 함. 그래서 답이 나오지 않는 경우가 있었음. 

for(auto &i:v)로 해결 가능.