[백준] 14890번 경사로

 

해당 문제는 크게 요구하는 알고리즘은 없는 것 같다. 문제를 풀 때 재귀를 사용했지만 그렇게 복잡하지 않았고 구현의 비중이 큰 문제다. 요즘 어려운 문제를 풀 때 조건 하나하나씩 생각하려고 한다. 이렇게 문제를 접근하다 보니 구현하는 데 있어서 큰 도움이 된다.

이 문제는 총 3가지 경우로 나뉜다.

1. 다음 칸이 현재 칸의 높이와 같을 경우

2. 다음 칸이 현재 칸의 높이보다 높을 경우

3. 다음 칸이 현재 칸의 높이보다 낮을 경우

여기서 이제 쪼개서 생각한다. 1번의 경우는 그대로 진행하면 되고 2번은 높이의 차가 1보다 큰 경우는 false. 만약 차이가 1이라면 앞에서부터 현재 칸까지 L개의 현재 칸과 높이가 같은 칸이 필요하다. 만약 L개 미만일 경우 false. 3번의 경우도 2번과 비슷하다. 높이의 차가 1보다 큰 경우 false. 차이가 1이라면 다음 칸부터 L개의 다음 칸과 높이가 같은 칸이 필요하다. 만약 L개 미만일 경우 false.

이렇게 나눠서 구현을 했다.

 

 

downDFS는 다음 칸이 낮은 경우 호출하는 함수고 upDFS는 다음 칸이 높은 경우 호출하는 함수다.

 

 

board에 값들을 입력 받은 후 행 방향의 길부터 검사를 한다. target은 현재 기준이 되는 값이다. 처음에는 첫 번째 값이 target이 된다. 그 후 for문을 통해 열을 0번째부터 N-1번째까지 체크한다. 

1. target과 해당 칸의 높이 차가 1보다 큰 경우 경사로를 놓을 수 없으므로 false.

2. 해당 칸이 target보다 작은 경우 downDFS를 호출한다.

  - downDFS에는 작아지기 시작하는 칸의 위치 (i, j), 현재 길의 진행 방향, 현재 줄의 경사로의 유무 를 인자로 넣는다.

3. 해당 칸이 target보다 큰 경우 upDFS를 호출한다.

  - upDFS에는 downDFS의 인자에서 target의 수를 추가하여 인자로 넣는다.

한 줄이 끝나면 canGo의 값에 따라 true면 answer의 값을 1 더한다.

 

 

낮은 칸의 개수가 L개보다 작은 경우 false를 리턴한다. 만약 L개 이상인 경우 위 예시에서 2 앞에 L개의 1에 경사로를 놓아준다. 그 후 아까 위에서 말한 3가지 경우의 수대로 나누어 진행한다. 진행 방향이 세로인 경우는 xpos, ypos, i, j값만 바꿔주고 나머지는 동일하다.

 

 

downDFS도 upDFS와 밑에 코드는 비슷하다. 위에는 낮아진 칸을 포함하여 경사로를 놓을 수 있는지 확인한 후 만약 L개의 칸보다 적으면 false를 리턴한다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>>board(101, vector<int>(101)); // 지도
int N, L, answer;

bool downDFS(int xpos, int ypos, char d, vector<bool> s); // 다음 칸이 한 칸 낮은 경우
bool upDFS(int counts, int xpos, int ypos, char d, vector<bool> s); // 다음 칸이 한 칸 높은 경우

// counts는 지도가 1 1 1 2 이런 경우 1의 갯수를 뜻함.
// xpos, ypos 는 한 칸 높은 칸의 위치
// d는 현재 진행 방향
// s는 해당 칸에 경사로 존재 여부
bool upDFS(int counts, int xpos, int ypos, char d, vector<bool> s) {
	// 낮은 칸의 갯수가 L보다 작은 경우
	// 경사로를 놓을 수 없다.
	if (counts < L)
		return false;

	int target = board[xpos][ypos];
	int scount = 0; // target 숫자의 갯수

	switch (d) {
	case 'R': { // 진행 방향이 가로
		// 앞 칸에 경사로를 놓아준다.
		for (int j = ypos - 1; j >= ypos - L; j--) {
			if (j < 0 or s[j])
				return false;
			s[j] = true;
		}

		
		for (int j = ypos; j < N; j++) {
			// 높이 차이가 1보다 큰 경우
			if (abs(board[xpos][j] - target) > 1)
				return false;
			
			if (board[xpos][j] == target)
				scount++;
			else if (board[xpos][j] < target) 
				return downDFS(xpos, j, 'R', s);
			
			else 
				return upDFS(scount, xpos, j, 'R', s);
		}
		break;
	}
	default: { // 진행 방향이 세로
		for (int i = xpos - 1; i >= xpos - L; i--) {
			if (i < 0 or s[i])
				return false;
			s[i] = true;
		}

		scount = 0;
		for (int i = xpos; i < N; i++) {
			if (abs(board[i][ypos] - target) > 1)
				return false;

			if (board[i][ypos] == target)
				scount++;
			else if (board[i][ypos] < target) 
				return downDFS(i, ypos, 'D', s);
			else 
				return upDFS(scount, i, ypos, 'D', s);
		}
	}
	}
	return true;
}

bool downDFS(int xpos, int ypos, char d, vector<bool> s) {
	int scount = 0;
	int target = board[xpos][ypos];

	switch (d) {
	case 'R': {
		// 3 2 2 2 인 경우에
		// 2의 갯수를 체크하는 과정
		for (int j = ypos; j < N; j++) {
			if (scount == L)
				break;

			if (board[xpos][j] == target)
				scount++;
			else
				break;
		}
		// 2의 갯수가 L보다 작은 경우
		if (scount != L)
			return false;

		// 길이 L만큼 경사로 설치
		for (int j = ypos; j < ypos + L; j++) 
			s[j] = true;

		scount = 0;
		for (int j = ypos + L; j < N; j++) {
			if (abs(board[xpos][j] - target) > 1)
				return false;

			if (board[xpos][j] == target)
				scount++;
			else if (board[xpos][j] < target) 
				return downDFS(xpos, j, 'R', s);
			else 
				return upDFS(scount, xpos, j, 'R', s);
		}
		break;
	}
	default: {
		for (int i = xpos; i < N; i++) {
			if (scount == L)
				break;

			if (board[i][ypos] == target)
				scount++;
			else
				break;
		}
		if (scount != L)
			return false;
		for (int i = xpos; i < xpos + L; i++) {
			s[i] = true;
		}

		scount = 0;
		for (int i = xpos + L; i < N; i++) {
			if (abs(board[i][ypos] - target) > 1)
				return false;

			if (board[i][ypos] == target)
				scount++;
			else if (board[i][ypos] < target) 
				return downDFS(i, ypos, 'D', s);
			else 
				return upDFS(scount, i, ypos, 'D', s);
		}
	}
	}

	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> L;

	answer = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}

	for (int i = 0; i < N; i++) { // 가로 진행 방향
		int target = board[i][0];
		int scount = 0; // target 숫자의 갯수
		bool canGo = true; // 경사로를 놓을 수 있는지 여부
		for (int j = 0; j < N; j++) {
			// target 숫자와 해당 칸의 높이 차이가 1보다 큰 경우
			if (abs(board[i][j] - target) > 1) {
				canGo = false;
				break;
			}

			if (board[i][j] == target)
				scount++;
			else if (board[i][j] < target) {
				vector<bool> v(N + 1, false);
				canGo = downDFS(i, j, 'R', v);
				break;
			}
			else {
				vector<bool> v(N + 1, false);
				canGo = upDFS(scount, i, j, 'R', v);
				break;
			}
		}
		if (canGo)
			answer++;
	}

	for (int j = 0; j < N; j++) { // 세로 진행 방향
		int target = board[0][j];
		int scount = 0;
		bool canGo = true;
		for (int i = 0; i < N; i++) {
			if (abs(board[i][j] - target) > 1) {
				canGo = false;
				break;
			}

			if (board[i][j] == target)
				scount++;
			else if (board[i][j] < target) {
				vector<bool> v(N + 1, false);
				canGo = downDFS(i, j, 'D', v);
				break;
			}
			else {
				vector<bool> v(N + 1, false);
				canGo = upDFS(scount, i, j, 'D', v);
				break;
			}
		}
		if (canGo)
			answer++;
	}

	cout << answer;

	return 0;
}