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

 문제 링크입니다. https://www.acmicpc.net/problem/21610

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

삼성 SW 역량테스트 기출문제입니다.

생각보단 귀찮은 구현 문제였습니다.

문제 조건

출력 예시

시간을 줄이기 위해 Queue에 좌표를 넣어놨습니다.

만들어야할 것은

1. 구름 좌표 이동

2. 해당 칸 물 증가

3. 다음 구름 찾기   입니다.

 

1. 구름 좌표 이동

	while (!place.empty()) {
		int x = place.front().first;
		int y = place.front().second;
		place.pop();
		int xx = x + dx[way] * num;
		int yy = y + dy[way] * num;
		if (xx > 0) xx = xx % N;
		else if (xx == 0) xx = N;
		else {
			while (1) {
				if (xx > 0) break;
				xx += N;
			}
		}

		if (yy > 0) yy = yy % N;
		else if (yy == 0) yy = N;
		else {
			while (1) {
				if (yy > 0) break;
				yy += N;
			}
		}
		if (xx == 0) xx = N;
		if (yy == 0) yy = N;

예를 들어 (2,2)에서 1방향으로 4번 이동한다고 가정하겠습니다.(N이 5라고 가정)

(2,2) -> (2,1) -> (2,5) -> (2, 4) -> (2, 3) 입니다.

(2, -2)가 되아할 좌표가 (2,3)이 된 모습이 보입니다.

이번에는 7방향으로 2번 움직인다고 하겠습니다.

(2,2) -> (3,2) ->(4,2) 입니다.

 

이를 종합해보면, (X,Y)일때, 음수 값이 있다면, N을 계속 더해주면서 1이상의 수가 나올때까지 반복하면 됩니다.

양수 값이 존재한다면, %N을 통해 나머지만 구해주면 됨을 알 수 있습니다.

저는 좌표를 1부터 시작한다고 가정했기에, 0 값이 존재한다면 해당 칸이 N임으로 N으로 바꿔줍니다.

 

 

2. 해당 칸 물 증가

	while (!Cloud.empty()) {
		int x = Cloud.front().first;
		int y = Cloud.front().second;
		Cloud.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dxx[i];
			int yy = y + dyy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
				if (copy_map[xx][yy] > 0) map[x][y]++;
			}
		}
	}

Queue를 통해, 구름의 이동 좌표를 Cloud queue에 넣어줬습니다.

해당 좌표를 받아서, 대각선 4방향 탐색을 통해 해당 칸에 물이 있는지를 확인합니다.

 

 

3. 다음 구름 찾기

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] >= 2 && check[i][j] == 0) {
				map[i][j] -= 2;
				place.push(make_pair(i, j));
			}	
			copy_map[i][j] = map[i][j];
		}
	}
	memset(check, 0, sizeof(check));

 check 배열에는 현재 구름의 위치가 저장되어 있습니다.

현재 물이 2칸 이상이며, 이전에 구름이 없는 경우, 해당 칸에 구름이 생기니 place queue에 넣어줍니다.

place queue의 경우, 구름 이동 좌표로써 사용됩니다.

 

 

문제 접근 방법

1. 처음 시작 구름 위치를 저장한다.

2. 구름을 방향, 횟수만큼 이동한다.

3. 이동한 구름 칸의 물을 1씩 증가한다.

4. 대각선 확인을 통해 물을 증가한다.

5. 새로운 구름을 확인한다.

6. 1~5 과정을 M만큼 반복한다.

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int N, M;
int map[51][51];
int copy_map[51][51];
int check[51][51];
int dx[9] = { 0,0,-1,-1,-1,0,1,1,1 };
int dy[9] = { 0,-1,-1,0,1,1,1,0,-1 };
int dxx[4] = { 1,1,-1,-1 };
int dyy[4] = { 1,-1,1,-1 };
queue<pair<int, int>> Cloud;
queue<pair<int, int>> place;
pair<int, int> move_cloud[101];

void cloud() {
	while (!Cloud.empty()) {
		int x = Cloud.front().first;
		int y = Cloud.front().second;
		Cloud.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dxx[i];
			int yy = y + dyy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
				if (copy_map[xx][yy] > 0) map[x][y]++;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] >= 2 && check[i][j] == 0) {
				map[i][j] -= 2;
				place.push(make_pair(i, j));
			}	
			copy_map[i][j] = map[i][j];
		}
	}
	memset(check, 0, sizeof(check));
}

void Move(int way, int num) {
	while (!place.empty()) {
		int x = place.front().first;
		int y = place.front().second;
		place.pop();
		int xx = x + dx[way] * num;
		int yy = y + dy[way] * num;
		if (xx > 0) xx = xx % N;
		else if (xx == 0) xx = N;
		else {
			while (1) {
				if (xx > 0) break;
				xx += N;
			}
		}

		if (yy > 0) yy = yy % N;
		else if (yy == 0) yy = N;
		else {
			while (1) {
				if (yy > 0) break;
				yy += N;
			}
		}
		if (xx == 0) xx = N;
		if (yy == 0) yy = N;
		map[xx][yy]++;
		copy_map[xx][yy]++;
		Cloud.push(make_pair(xx, yy));
		check[xx][yy] = 1;
	}
	cloud();
}

void first_input() {
	for (int i = N - 1; i <= N; i++) {
		for (int j = 1; j <= 2; j++) {
			place.push(make_pair(i, j));
		}
	}
}

void solve() {
	int ans = 0;
	first_input();
	for (int i = 0; i < M; i++) {
		Move(move_cloud[i].first, move_cloud[i].second);
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] > 0) ans += map[i][j];
		}
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			copy_map[i][j] = map[i][j];
		}
	}
	for (int i = 0; i < M; i++) {
		cin >> move_cloud[i].first >> move_cloud[i].second;
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!