[백준] 5212. 지구 온난화 (C++)

Key

변경된 결과를 원본 지도에 반영하면 다음 값 계산에 영향을 미친다.

'지도를 넘어간 부분은 모두 바다' 라는 조건이 있다.

 

Idea

처음에는 원본 지도 크기가 동적이므로 벡터로 설정해주고 타입은 char로 했다. 그런데 R, C 크기가 최대 10밖에 안되므로 굳이 벡터로 설정해주지 않아도 될듯하여 정적 배열로 바꿨다. 지도를 넘어간 부분은 모두 바다이고, 사방을 탐색해야하므로 계산할 때 편하게 패딩을 줬다. (12X12)

 

그리고 항상 내가 간과하는 부분인데, 이렇게 입력값을 yes or no로 판단할 수 있는 경우엔 bool 타입으로 변경해서 사용하는 게 훨씬 편하다.

 

로직은 다음과 같다.

 

1. 변경된 결과를 바로 반영하면 안 되므로 원본 데이터를 저장하는 배열인 map과 바뀐 결과를 저장하는 배열인 final을 만들고 false로 초기화했다.

2. 그리고 입력값이 X면 해당 위치를 true로 바꿨다.

3. changeMap 함수는 50년 후 섬의 모습을 반영하는 함수인데, 지도 전체를 탐색하며 X(true)가 나타나면 X의 사방을 탐색하고, 사방 중 바다가 있으면 cnt 값을 증가시킨다. 사방 탐색이 끝난 후 바다 개수가 3개 미만이면 final 지도에 반영한다.

 

이렇게 하면 50년 후 지도 모습은 나온다.

 

4. 이제 지도 크기에 맞춰 출력해야한다. '지도의 크기는 모든 섬을 포함하는 가장 작은 직사각형이다.'

원본 지도 크기에 맞춰 startX, startY, endX, endY값을 초기화하고 final 지도에서 X가 나올 때마다 min, max 함수로 startX, startY, endX, endY 값을 재정의한다.

5. 구해진 최소 직사각형 크기로 final 지도를 출력한다.

 

Code

#include <iostream>
#include <vector>

using namespace std;

bool map[12][12] = { false, };
bool final[12][12] = { false, };
int nx[] = { -1, 0, 1, 0 };
int ny[] = { 0, 1, 0, -1 };

// 50년 후 섬의 모습
void changeMap(int R, int C) {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (map[i][j]) {
				int cnt = 0;
				for (int k = 0; k < 4; k++) {
					int nextX = i + nx[k];
					int nextY = j + ny[k];
					if (!map[nextX][nextY]) cnt++;
				}
				if (cnt < 3) final[i][j] = true;
			}
		}
	}
}

int main() {

	int R = 0, C = 0;
	char input = ' ';

	cin >> R >> C;

	// X면 해당 위치는 true
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> input;
			if (input == 'X') map[i][j] = true;
		}
	}

	changeMap(R, C);

	// 50년 후 섬의 모습에서 섬의 크기를 다시 구하여 출력
	int startX = R;
	int startY = C;
	int endX = 0;
	int endY = 0;

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (final[i][j]) {
				startX = min(startX, i);
				startY = min(startY, j);
				endX = max(endX, i);
				endY = max(endY, j);
			}
		}
	}

	for (int i = startX; i <= endX; i++) {
		for (int j = startY; j <= endY; j++) {
			if (final[i][j]) cout << "X";
			else cout << ".";
		}
		cout << "\n";
	}

	return 0;
}

 

회고

본격적으로 코딩테스트를 준비하며 회고 글을 작성해볼까한다.

세 달만에 알고리즘을 풀었고 오랜만이라 그런가 쉬운 문제인데 문제 해석도 잘못해서 시간을 날렸다.

30분 타이머를 쟀는데 문제 해석에 15분 쓰고 구현을 30%정도밖에 못했다.

난 언제쯤 알고리즘이 안 무서워질까?

 

일주일 후엔 더 나은 내가 되어있길 바라며.... 

 

내가 생각하기 어려웠던 부분
1. 지도 크기가 변하는 것을 어떻게 반영할지

2. 지도 출력을 어떻게 해야할지 (1번과 연관된 부분)

 

내가 생각하지 못하고 넘어간 부분

1. 변화된 걸 바로 적용하면 다음 계산에 영향을 줌

2. 값을 그대로 쓰지 말고 bool로 바꾸면 편함

3. 지도를 넘어간 부분은 모두 바다라는 조건에 유의