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

 

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

 

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

14890번: 경사로

---

 

 

해결전략

 

구현 

---

 

 

정답 코드

 

#include <iostream>
#include <vector>
using namespace std;

int n, l;   // n: 지도의 크기, l: 경사로의 길이
int answer;
vector<vector<int>> v;

bool RoadCheckY(int y) // y번째 행에 대해 경사로를 설치할 수 있는지 검사
{
    vector<vector<bool>> ch(n, vector<bool>(n, false));

    for (int i = 0; i < n - 1; i++)
    {
        if (v[y][i] == v[y][i + 1]) continue; // 현재 칸과 다음 칸의 높이가 같으면 계속 진행
        else if (v[y][i] < v[y][i + 1]) {     // 현재 칸이 다음 칸보다 낮을 때
            if (v[y][i + 1] - v[y][i] != 1) return false; // 높이 차이가 1이 아니면 경사로를 설치할 수 없음
            int tmp = i;
            int cnt = l; // 경사로 길이만큼 카운트
            while (tmp >= 0 && cnt) {
                if (v[y][tmp] == v[y][i] && ch[y][tmp] == false) { // 경사로를 설치할 수 있으면 계속 진행
                    ch[y][tmp] = true;
                    cnt--;
                }
                else return false;

                tmp--;
            }
            if (cnt > 0) return false; // 경사로를 설치할 공간이 부족하면 false
        }
        else if (v[y][i] > v[y][i + 1]) {     // 현재 칸이 다음 칸보다 높을 때
            if (v[y][i] - v[y][i + 1] != 1) return false;
            int tmp = i + 1;
            int cnt = l; // 경사로 길이만큼 카운트
            while (tmp < n && cnt) {
                if (v[y][i + 1] == v[y][tmp] && ch[y][tmp] == false) { // 경사로를 설치할 수 있으면 계속 진행
                    ch[y][tmp] = true;
                    cnt--;
                }
                else return false;

                tmp++;
            }
            if (cnt > 0) return false; // 경사로를 설치할 공간이 부족하면 false
        }
    }

    return true;
}

bool RoadCheckX(int x)
{
    vector<vector<bool>> ch(n, vector<bool>(n, false));

    for (int i = 0; i < n - 1; i++)
    {
        if (v[i][x] == v[i + 1][x]) continue;
        else if (v[i][x] < v[i + 1][x]) {
            if (v[i + 1][x] - v[i][x] != 1) return false;
            int tmp = i;
            int cnt = l; 
            while (tmp >= 0 && cnt) {
                if (v[tmp][x] == v[i][x] && ch[tmp][x] == false) {
                    ch[tmp][x] = true;
                    cnt--;
                }
                else return false;

                tmp--;
            }
            if (cnt > 0) return false;
        }
        else if (v[i][x] > v[i + 1][x]) {
            if (v[i][x] - v[i + 1][x] != 1) return false;
            int tmp = i + 1;
            int cnt = l;
            while (tmp < n && cnt) {
                if (v[i + 1][x] == v[tmp][x] && ch[tmp][x] == false) {
                    ch[tmp][x] = true;
                    cnt--;
                }
                else return false;

                tmp++;
            }
            if (cnt > 0) return false;
        }
    }

    return true;
}

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

	cin >> n >> l;
	v.resize(n, vector<int>(n));
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> v[y][x];
		}
	}

    for (int i = 0; i < n; i++) {
        if (RoadCheckY(i)) answer++; // 행 검사
        if (RoadCheckX(i)) answer++; // 열 검사
    }

	cout << answer;

	return 0;
}

 

 

---