SWEA 4014번 [모의 SW 역량테스트] 활주로 건설 C++ 구현, 시뮬레이션

리뷰

쉬운 구현, 시뮬레이션 문제였다, 접목할 알고리즘은 딱히 없는듯

 

문제 풀이

1. 각 테스트 케이스마다 ans를 0으로 초기화 해주고, 한변의 길이 n과 경사로의 길이 x, 2차원 맵 정보를 입력 받아준다.
2. 각 행의 0번째 열부터 n - 1번째 열까지 탐색을 돌리고, 각 열의 0번째 행부터 n - 1번째 행까지 탐색을 돌려준다.
3. 맵의 범위를 벗어날 때 까지 각 행과 열을 증가시키며 탐색을 한다.
4. 만약 현재보다 2이상 큰 땅을 만난다면 더이상 탐색할 필요가 없이 return 해주면 된다.
5. 만약 더 높은 땅을 만난 경우 현재 위치로부터 x - 1 이전의 땅에 경사로를 설치할 수 있는지 체크해 준다.
6. 설치가 가능하다면 현재 높이를 높여주고, 뒤쪽의 땅에 경사로 설치를 하고 한칸 올라왔다는 표시를 해준다.
7. 더 낮은 땅을 만난 경우 현재 위치로부터 x - 1 이후의 땅에 경사로를 설치할 수 있는지 체크해 준다.
8. 설치가 가능하다면 현재 높이를 내려주고, 앞쪽의 땅에 경사로 설치를 하고 한칸 내려왔다는 표시를 해준다.
9. 동일한 땅을 만날때의 로직은 따로 짜주지 않았다, 각 경사로 설치 변수를 줄여주고 좌표는 증가시킨다.
10. solution이 완료되고 난 후에 각 테스트 케이스 마다 ans를 출력해 주면 된다.

 

참고 사항

예시 1

위의 경우 flag는 -1이 되며, d는 x, g는 2 * x로 초기화 해준다.

예시 2

이후 계속 탐색을 하다 또 낮은 땅을 만났는데 d가 0보다 큰 경우 위와 같은 케이스이므로 리턴해 주면 된다.

예시 3

이후 계속 탐색을 하다 높은 땅을 만났는데 g가 0보다 큰 경우 위와 같은 케이스이므로 리턴해 주면 된다.

flag를 통해 높은 땅을 만났는지 낮은 땅을 만났는지를 관리해 주는 이유가 이 케이스 때문이다.

 

예시 4

평지를 걷다가 높은 땅을 만난 경우 u를 x로 설정해 주고 flag를 1로 설정해 준다.

경사로를 위쪽으로 설치했는데 예시2와 동일한 경우와 예시3 같은 경우를 잘 예외처리 해주면 된다.

 

정답 코드

#include<iostream>

using namespace std;

int tc, n, x, ans;
int lst[20][20];
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };

// ans 초기화
void init() {
	ans = 0;
}

// 입력
void input() {
	cin >> n >> x;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
		}
	}
}

// 왼쪽에서 오른쪽으로 탐색
void col_bfs(int sx, int sy) {
	int ny = sy + 1, u = 0, d = 0, g = 0, flag = 0, ch = lst[sx][sy];
	while (0 <= ny && ny < n) {
		// 2이상 차이나면 탐색 그만
		if (abs(lst[sx][ny] - ch) > 1) return;
		// 더 높은 땅을 만났을 때
		if (lst[sx][ny] > ch) {
			if (u > 0) return;
			if (ny - x < 0) return;
			if (flag == -1 && g > 0) return;
			ch++;
			u = x;
			flag = 1;
		}
		// 낮은땅을 만났을 때
		else if (lst[sx][ny] < ch) {
			if (ny + x > n) return;
			if (d > 0) return;
			ch--;
			flag = -1;
			d = x;
			g = 2 * x;
		}
		u--;
		d--;
		g--;
		ny++;
	}
	//cout << "col : " << sx << " " << sy << "\n";
	ans++;
}

// 위에서 아래로 탐색 좌표 위치만 다르고 나머지 내용은 상동
void row_bfs(int sx, int sy) {
	int nx = sx + 1, u = 0, d = 0, g = 0, flag = 0, ch = lst[sx][sy];
	while (0 <= nx && nx < n) {
		if (abs(lst[nx][sy] - ch) > 1) return;
		if (lst[nx][sy] > ch) {
			if (u > 0) return;
			if (nx - x < 0) return;
			if (flag == -1 && g > 0) return;
			ch++;
			u = x;
			flag = 1;
		}
		else if (lst[nx][sy] < ch) {
			if (nx + x > n) return;
			if (d > 0) return;
			ch--;
			flag = -1;
			d = x;
			g = 2 * x;
		}
		u--;
		d--;
		g--;
		nx++;
	}
	//cout << "row : " << sx << " " << sy << "\n";
	ans++;
}

// 행 열 각각 0부터 탐색을 돌려버렷
void solution() {
	for (int i = 0; i < n; i++) {
		col_bfs(i, 0);
		row_bfs(0, i);
	}
}

int main() {
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		init();
		input();
		solution();
		cout << "#" << t << " " << ans << "\n";
	}
}