백준 14890번_경사로

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

14890번: 경사로

풀이방법

1. 1 방향으로 한번, 2 방향으로 한번 완전탐색을 돌린다.

이렇게 두번 완전탐색할것

2. 탐색하며 바꿔야 할것

 

 2.1 옆에 값과 현재 값이 같을때 -> 그냥 통과

 2.2 옆에 값과 현재 값이 다를때 

 

  2.2.1 옆에 값과 현재 값의 차이가 1이하일때 

     2.2.1.1 현재 값 > 옆의 값 

       2.2.1.1.1 visited 에 걸릴때 -> 이 줄은 안됨

       2.2.1.1.2 안걸릴때 

     2.2.1.2 현재 값 < 옆의 값

       ...위와 동일

 

  2.2.2 옆에 값과 현재 값의 차이가 1초과일때 -> 이 줄은 안됨

 

 위에 있는걸 다 처리하면된다.

 

---

전체코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int map[101][101];
int n, l;

bool checkLine(vector<int> line)
{
	int len = (int)line.size();

	vector<int> visit(line.size());

	for (int i = 0; i < len - 1; i++)
	{
		int firstidx = i;
		int secondidx = i + 1;
		int first = line[i];
		int second = line[i + 1];

		//같은 높이면 continue
		if (first == second)
			continue;

		//높이 차이가 1이상 나면 return false;
		if (abs(first - second) > 1)
			return false;

		//왼쪽이 더 높을때
		if (first - second == 1)
		{
			//옆에 여유 공간이 있는지 확인
			for (int k = 1; k <= l; k++)
			{
				int nextidx = firstidx + k;
				if (nextidx > n - 1)
					return false;
				if (visit[nextidx] == 1)
					return false;
				//여유공간이 있을시 이것과 높이차이가 모두 1인지 확인
				if (!abs(line[nextidx] - first) == 1)
					return false;
				else
				{
					visit[nextidx] = 1;
				}
			}
		}

		//오른쪽이 더 높을때
		else if (second - first == 1)
		{
			//옆에 여유 공간이 있는지 확인
			for (int k = 1; k <= l; k++)
			{
				int nextidx = secondidx - k;
				if (nextidx < 0)
					return false;
				if (visit[nextidx] == 1)
					return false;
				//여유공간이 있을시 이것과 높이차이가 모두 1인지 확인
				if (!abs(line[nextidx] - second) == 1)
					return false;
				else
				{
					visit[nextidx] = 1;
				}
			}
		}

	}

	return true;
}

int main()
{
	cin >> n >> l;

	//map만들기
	for (int i = 0; i < n; i++)
	{
		int value;
		for (int j = 0; j < n; j++)
		{
			cin >> value;
			map[i][j] = value;
		}
	}

	int cnt = 0;
	//되는 길 찾아보기, 가로
	for (int i = 0; i < n; i++)
	{
		vector<int> line;
		for (int j = 0; j < n; j++)
		{
			line.push_back(map[i][j]);
		}

		//여기서 한줄씩 계산
		if (checkLine(line))
			cnt++;

	}

	//세로
	for (int j = 0; j < n; j++)
	{
		vector<int> line;
		for (int i = 0; i < n; i++)
		{
			line.push_back(map[i][j]);
		}

		//여기서 한줄씩 계산
		if (checkLine(line))
			cnt++;
	}

	cout << cnt;

	return 0;
}

---

후기

다시 풀려다가 그냥 시뮬레이션이기도 하고 구현량이 많은것뿐이라 예전에 풀었던 코드를 올린다.

나같은 경우에는 한줄한줄을 vector에 넣어서 처리하고 그게 만족하면 cnt를 올리는 식으로 코드를 짰다.