백준 14890번 경사로

🔒[문제 url]

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

🔑알고리즘

흔히 말하는 빡구(빡센 구현) 문제..
모든 구현 문제가 그렇듯, 적용할 알고리즘이 있지는 않기에 피지컬이 요구되긴하나, 그만큼 처음에 문제를 어떻게 설계할지가 중요했던 문제.

1. 지도의 가로, 세로 모두 따져야한다. 각 함수를 따로 구현하는 것이 아닌 vector에 가로, 세로를 넣어줌으로써 하나의 함수로 처리.
2. vector를 순회하며 길이 되는지 안 되는지 판별. 여기서 따져봐야할 케이스는 4가지
   • 모두 경사가 같은 경우
   • 경사가 1 높은 땅을 만난 경우
     - 지금까지 경사가 같은 땅이 L이상이면 길
   • 경사가 1 낮은 땅을 만난 경우
     - 앞으로 경사가 같은 땅이 L이상이면 길
   • 경사가 2이상 차이나는 땅을 만난 경우 == 길이 아님

🐾부분 코드

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> l;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	// vector에 가로 세로를 넣음으로써, 길판정 함수를 하나로 구현!
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			v[i].push_back(map[i][j]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			v[i + n].push_back(map[j][i]);
}

<입력 함수>
벡터 v의 0번째 index~ n-1번째 index까지는 행을,
n번째 index부터 2n - 1번째 index까지는 열을 push한다.

bool isRoad(int line)
{
	/*
	경우의 수는 4가지.
	1. 모두 경사가 같음
	2. 높아지는 경사로 -> 1 높은 칸 만난 경우
	3. 낮아지는 경사로 -> 1 낮은 칸 만난 경우
	4. 길 불가능 -> 경사가 2 이상 차이

	경사로를 설치할 경우,
	2번 : 1 높은 칸을 만났을 경우 sameHeight가 L이상
	3번 : 1 낮은 칸을 만났을 경우 앞으로의 sameHeight가 L이상
	*/


	int sameHeight = 1; // 경사가 같은 땅의 연속된 수
	for (int i = 1; i < n; i++)
	{
		
		// 1번
		if (v[line][i] == v[line][i - 1])
		{
			sameHeight++;
			if (sameHeight == n)
			{
				ans++;
				return true;
			}

		}

		// 2번 높아지는 경사로
		else if (v[line][i] == v[line][i - 1] + 1)
		{
			if (sameHeight >= l)
			{// 지금까지의 sameHeight가 l 이상이면 설치
				sameHeight = 1;
			}
			else return false;
		}

		// 3번 낮아지는 경사로
		else if (v[line][i] + 1 == v[line][i - 1])
		{
			sameHeight = 1; // 이후 sH 갯수
			bool stop = false;
			// 이후의 sameHeight가 L 이상인지 검사
			for (int j = 0; j < l - 1; j++)
			{
				if ((i + j + 1 < n) && v[line][i + j] == v[line][i + j + 1]) sameHeight++;
				else return false;
			}

			if(sameHeight == l)
			{
				sameHeight = 0;
				i += l - 1; // 경사로 길이만큼 건너뛰기
			}
		}

		// 4번 경사 차이 2이상
		else if (abs(v[line][i] - v[line][i - 1]) > 1) return false;
	}
	ans++;
	return true;
}

<길인지 아닌지 판별하는 함수>
sameHeight의 갱신과, 3번(낮아지는 경사로) 케이스에서

if ((i + j + 1 < n) && v[line][i + j] == v[line][i + j + 1]) sameHeight++;
// 범위 처리

i += l - 1; // // 경사로 길이만큼 건너뛰기

위 두 코드만 캐치했다면 어렵지않게 풀 수 있는 문제.
나는 캐치를 못해서 오래 걸렸다^^

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stdio.h>
#include <ctime>
#include <memory.h> // memset
#include <numeric>
#include <stack>
#include <sstream>
using namespace std;

int n, l;
int map[100][100];
vector<int> v[200];

int ans = 0;

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> l;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	// vector에 가로 세로를 넣음으로써, 길판정 함수를 하나로 구현!
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			v[i].push_back(map[i][j]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			v[i + n].push_back(map[j][i]);
}



bool isRoad(int line)
{
	/*
	경우의 수는 4가지.
	1. 모두 경사가 같음
	2. 높아지는 경사로 -> 1 높은 칸 만난 경우
	3. 낮아지는 경사로 -> 1 낮은 칸 만난 경우
	4. 길 불가능 -> 경사가 2 이상 차이

	경사로를 설치할 경우,
	2번 : 1 높은 칸을 만났을 경우 sameHeight가 L이상
	3번 : 1 낮은 칸을 만났을 경우 앞으로의 sameHeight가 L이상
	*/


	int sameHeight = 1; // 경사가 같은 땅의 연속된 수
	for (int i = 1; i < n; i++)
	{
		
		// 1번
		if (v[line][i] == v[line][i - 1])
		{
			sameHeight++;
			if (sameHeight == n)
			{
				ans++;
				return true;
			}

		}

		// 2번 높아지는 경사로
		else if (v[line][i] == v[line][i - 1] + 1)
		{
			if (sameHeight >= l)
			{// 지금까지의 sameHeight가 l 이상이면 설치
				sameHeight = 1;
			}
			else return false;
		}

		// 3번 낮아지는 경사로
		else if (v[line][i] + 1 == v[line][i - 1])
		{
			sameHeight = 1;
			// 이후의 sameHeight가 L 이상인지 검사
			for (int j = 0; j < l - 1; j++)
			{
				if ((i + j + 1 < n) && v[line][i + j] == v[line][i + j + 1]) sameHeight++;
				else return false;
			}

			if(sameHeight == l)
			{
				sameHeight = 0;
				i += l - 1; // 경사로 길이만큼 건너뛰기
			}
		}

		// 4번 경사 차이 2이상
		else if (abs(v[line][i] - v[line][i - 1]) > 1) return false;
	}
	ans++;
	return true;
}

bool check(int line)
{

	
	if(isRoad(line)) return true;

	return false;

}

void SOLVE()
{

	// 가로 n줄 탐색후 세로 n줄 탐색`
	for (int i = 0; i < 2 * n; i++) check(i);

	cout << ans;

}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

우선, 접근 방법을 떠올리는데 시간이 꽤 걸렸다.
이후, sameHeight 갱신과 경사로 탐색중 out of range가 금방 잡히지 않아 애먹었지만, 그래도 뭐가 잘못됐지는 알았기에 맨땅에 헤딩하는 느낌은 들지않아 덜 힘들었던 문제..🤣
다음에 같은 상황을 마주친다면 그림을 통해 케이스에 대해 정확하게 짚어가며 풀어보자.