[백준] 14890번 경사로 C++

 

https://www.acmicpc.net/problem/14890

14890번: 경사로

문제이해

우선 N이 그렇게 크지 않아 문제를 보자마자 완전탐색이라는 생각이 들었다.

그리고 문제의 조건이 굉장히 많아 보이는데 생각해보면 간단히 해결되는 문제인 것 같다.

제일 중요한 것은, 오르막이나 내리막을 만났을 때 낮은 길에 L만큼의 경사로를 설치할 수 있느냐? 없느냐?

이것만 탐색해준다면 쉽게 해결되는 문제이다.

나는 row마다 탐색하는 함수와 col마다 탐색하는 함수를 따로 썼는데 둘 다 로직이 비슷해서 하나의 함수로 합치고 싶었지만...더 깔끔해질 것 같지 않아서 결국 따로 작성했다. ㅠㅠㅠ

 

풀이과정

1. 한 행씩 for문을 통해 탐색한다.
2. 현재 위치와 다음 위치의 높이차(diff = current - next)를 계산한다. 해당 값이 1이라면 현재 위치가 높은 위치이니 내리막길을 설치해야 할 것이고, -1이라면 낮은 위치이니 오르막길을 설치해야 할 것이다. 해당값이 0이라면 continue로 계속 탐색을 진행하고, 그 외의 값이라면 해당 row 탐색은 중단하고 다음 row로 넘어간다.
3. 문제 조건에 따르면 경사로를 설치할 때 무조건 L 길이만큼 설치해야 한다.
   1. diff == 1 이라면 (next ≤ idx ＜ next + L)의 idx 값이 모두 map[row][next] 값과 같아야 경사로를 설치 할 수 있다.
   2. 해당 idx를 탐색하는 도중 범위를 벗어나거나 다른 값이 있다면 해당 행에는 경사로를 설치할 수 없으므로 break한다.
   3. 위의 사항만 구현할 경우 예외상황이 발생한다. 해당 행의 값이 (3 3 2 2 3 3) 일 경우이다.
   4. 경사로를 설치한 자리에는 다시 설치할 수 없다. 따라서 row_visit(행 탐색할 때), col_visit(열 탐색할 때)배열을 선언하여 3-1번 에서 경사로를 설치할 때 마다 row_visit의 값을 설정해준다.
   5. 또한 3-1의 조건을 수정해야 한다. map[row][next] == map[row][idx] && !row_visit[row][idx] 이 두개 조건을 만족해야 경사로를 설치할 수 있다.
4. 해당 행의 끝까지 탐색했다면 answer 값을 1 더해준다.
5. 열 탐색은 1 ~ 4번 까지 행 열 값만 바꾸고 진행하면 된다.

 

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

int N, L, answer;
vector<vector<int>> map;
vector<vector<bool>> rvisit, cvisit;

void solution_row() {
	for (int r = 0; r < N; r++) {
		bool success = true;
		for (int c = 0; c < N - 1; c++) {
			// diff == 1이면 다음 길까지 내리막길
			// diff == -1이면 다음 길까지 오르막길
			int diff = map[r][c] - map[r][c + 1];
			if (diff == 0)
				continue;
			else if (abs(diff) > 1) {
				success = false;
				break;
			}
			int height = diff == 1 ? map[r][c + 1] : map[r][c];
			int startidx = diff == 1 ? c + 1 : c - L + 1;
			int endidx = diff == 1 ? c + L : c;
			if (startidx < 0 || endidx >= N) {
				success = false;
				break;
			}
			int wayCount = 0;

			for (int k = startidx; k <= endidx; k++) {
				if (map[r][k] == height && !rvisit[r][k]) {
					wayCount++;
					rvisit[r][k] = true;
				}
				else
					break;
			}

			if (wayCount == L) {
				diff == 1 ? c = endidx - 1 : c = endidx;
			}
			else {
				success = false;
				break;
			}
		}
		if (success)
			answer++;
	}
}
void solution_col() {
	for (int c = 0; c < N; c++) {
		bool success = true;
		for (int r = 0; r < N - 1; r++) {
			// diff == 1이면 다음 길까지 내리막길
			// diff == -1이면 다음 길까지 오르막길
			int diff = map[r][c] - map[r + 1][c];
			if (diff == 0)
				continue;
			else if (abs(diff) > 1) {
				success = false;
				break;
			}
			int height = diff == 1 ? map[r + 1][c] : map[r][c];
			int startidx = diff == 1 ? r + 1 : r - L + 1;
			int endidx = diff == 1 ? r + L : r;
			if (startidx < 0 || endidx >= N) {
				success = false;
				break;
			}
			int wayCount = 0;

			for (int k = startidx; k <= endidx; k++) {
				if (map[k][c] == height && !cvisit[k][c]) {
					wayCount++;
					cvisit[k][c] = true;
				}
				else
					break;
			}

			if (wayCount == L) {
				diff == 1 ? r = endidx - 1 : r = endidx;
			}
			else {
				success = false;
				break;
			}
		}
		if (success)
			answer++;
	}
}
int main() {
	cin >> N >> L;
	map.resize(N, vector<int> (N, 0));
	rvisit.resize(N, vector<bool>(N, false));
	cvisit.resize(N, vector<bool>(N, false));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];
	
	solution_row();
	solution_col();
	printf("%d\n", answer);
	return 0;
}