[BOJ][백준 14890] 경사로 - C++

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

14890번: 경사로

백준 사이트의 14890번 문제, 경사로 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

등산로 설치가 가능한 경우, 불가능한 경우

경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

---

1. 문제풀이 아이디어

• 한 줄씩 확인하는 함수를 만들자.
• 한 줄을 쭉보며 경사로를 놓는 조건과 놓을 수 없는 조건을 체크해주면 된다.
• 조건을 빼먹지 않도록 조심하자.
• 행과 열을 모두 확인해야하는데, 행을 기준으로 코드를 짜고,
• 열은 배열을 회전하여 넣어주면 된다.

---

2. 코드 핵심 부분

1) 각 행마다 경사로가 설치 가능한지 체크하는 함수,

   행과 열 모두 체크해야 하는것은 main에서 배열을 회전시켜 줌으로써 해결하였고,

   경사로를 놓을 수 없는 경우 모두를 체크하여 다 통과할 경우 가능하게 해주었다.

 

   처음에 중복의 경우를 처리하지 않아 값이 틀리게 나왔었는데,

   이를 visited 배열을 투입하여 해결하였다.

// 각 행마다 경사로 설치 가능한지 체크하는 함수
void solve(int Row) {
	int visited[100] = { 0 };

	for (int Col = 1; Col < N; Col++) {
		// 높이가 달라지는 구간만 비교하면 됨.
		// 만약 이전과의 차이가 2이상이면 그냥 불가능
		if (abs(Map[Row][Col] - Map[Row][Col - 1]) >= 2)
			return;

		// 이전보다 높은경우, Col -1 ~ Col - L이 모두 같아야함.
		if (Map[Row][Col] > Map[Row][Col - 1]) {
			// 범위 밖이면 탈락
			if (Col - L < 0)
				return;
			for (int i = Col - L; i <= Col - 1; i++) {
				// 만약 다르면 탈락
				if (Map[Row][i] != Map[Row][Col - 1])
					return;
				// 이미 경사로를 놨으면 탈락
				if (visited[i] == 1)
					return;
				visited[i] = 1;
			}
		}

		// 이전보다 낮은경우, Col ~ Col + L - 1이 모두 같아야함.
		else if (Map[Row][Col] < Map[Row][Col - 1]) {
			// 범위 밖이면 탈락
			if (Col + L - 1 >= N)
				return;
			for (int i = Col; i <= Col + L - 1; i++) {
				// 만약 다르면 탈락
				if (Map[Row][i] != Map[Row][Col])
					return;
				// 이미 경사로를 놨으면 탈락
				if (visited[i] == 1)
					return;
				visited[i] = 1;
			}
		}
	}
	// 모두 통과했으면 경사로 가능
	Ans++;
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/*
1. 문제읽기
경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.
경사로를 놓은 곳에 또 경사로를 놓는 경우
낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
경사로를 놓다가 범위를 벗어나는 경우
*/

/*
2. 아이디어
	한 줄씩 확인하는 함수를 만들자.
	한 줄을 쭉보며 경사로를 놓는 조건과 놓을 수 없는 조건을 체크해주면 된다.
	조건을 빼먹지 않도록 조심하자.
	행과 열을 모두 확인해야하는데, 행을 기준으로 코드를 짜고,
	열은 배열을 회전하여 넣어주면 된다.
*/

// 필요 인자들
int N; // 지도 크기 NxN (2 ≤ N ≤ 100)
int L; // 경사로의 길이 (1 ≤ L ≤ N)
int Map[100][100]; // 행체크 지도
int cMap[100][100]; // 열체크 지도
int Ans;

// 값 입력받는 함수
void input() {
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
			cMap[j][i] = Map[i][j];
		}
	}
}

// 각 행마다 경사로 설치 가능한지 체크하는 함수
void solve(int Row) {
	int visited[100] = { 0 };

	for (int Col = 1; Col < N; Col++) {
		// 높이가 달라지는 구간만 비교하면 됨.
		// 만약 이전과의 차이가 2이상이면 그냥 불가능
		if (abs(Map[Row][Col] - Map[Row][Col - 1]) >= 2)
			return;

		// 이전보다 높은경우, Col -1 ~ Col - L이 모두 같아야함.
		if (Map[Row][Col] > Map[Row][Col - 1]) {
			// 범위 밖이면 탈락
			if (Col - L < 0)
				return;
			for (int i = Col - L; i <= Col - 1; i++) {
				// 만약 다르면 탈락
				if (Map[Row][i] != Map[Row][Col - 1])
					return;
				// 이미 경사로를 놨으면 탈락
				if (visited[i] == 1)
					return;
				visited[i] = 1;
			}
		}

		// 이전보다 낮은경우, Col ~ Col + L - 1이 모두 같아야함.
		else if (Map[Row][Col] < Map[Row][Col - 1]) {
			// 범위 밖이면 탈락
			if (Col + L - 1 >= N)
				return;
			for (int i = Col; i <= Col + L - 1; i++) {
				// 만약 다르면 탈락
				if (Map[Row][i] != Map[Row][Col])
					return;
				// 이미 경사로를 놨으면 탈락
				if (visited[i] == 1)
					return;
				visited[i] = 1;
			}
		}
	}
	// 모두 통과했으면 경사로 가능
	Ans++;
}

// 메인함수
int main() {

	// input
	input();

	// solve
	// 각 행마다 실행
	for (int i = 0; i < N; i++) {
		solve(i);
	}
	// 뒤집어 준다.
	memcpy(Map, cMap, sizeof(Map));
	// 각 열마다 실행
	for (int i = 0; i < N; i++) {
		solve(i);
	}
	
	// output
	cout << Ans;

	return 0;
}

---

4. 문제 풀이를 마치며..

채점 결과

아이디어가 핵심인 문제였고, 그만큼 다양한 풀이가 존재하는 문제다.

행과 열을 조사하는 것을 어떻게 처리할지,

등산로 설치가능 여부를 어떻게 판단할지 아이디어를 생각해야 한다.

 

이 문제는 사실 똑같은 유형을 한달 전에 풀어본적이 있다.

그때는 예외처리를 제대로 하지 못하여서 풀이에 시간이 더 걸렸었는데,

이번에 풀 때는 미리 경우를 다 정리해두고 그에 맞춰 하나하나 상황을 처리해가는 방식으로 해서

더 쉽게 풀 수 있었던 것 같다.