백준 14890번: 경사로

[문제 링크]

14890번: 경사로

---

문제를 풀기에 앞서 문제에서 주어진 지도와 경사로, 그리고 지도와 경사로를 이용해 지나갈 수 있는 길인지 파악하는 역할을 하는 사람을 클래스 다이어그램으로 표현하였다.

 

사람은 지형이 그려진 지도와 설치할 수 있는 경사로를 "가지고" 있다고 볼 수 있기 때문에

"사람은 지도와 경사로를 포함한다." 라는 has-A 관계가 성립된다.

따라서 필자는 클래스 다이어그램을 다음과 같이 작성하였다.

사람과 지도, 경사로의 클래스 다이어그램

 

알고리즘은 다음과 같다.

1. 입력받은 정보를 통해 지도와 경사로 객체를 생성한다.

2. 지도와 경사로 객체를 속성으로 가지는 사람 객체를 생성한다.

3. 한쪽 끝에서 반대쪽 끝으로 가는 길을 찾는 것이기 때문에 1열의 모든 좌표에서 아래방향으로 탐색하고, 1행의 모든 좌표에서 오른쪽 방향으로 탐색하여 가능한 길의 갯수를 샌다.

 3-1. IF 현재 지형의 높이가 이전 지형의 높이와 같다면 경사로를 놓을 필요 없이 다음 지형으로 넘어간다.

ELSE IF 현재 지형의 높이가 더 낮다면 현재 지형을 시작으로 경사로를 놓을 수 있는지 검사한다. 경사로를 놓을 수 없다면 탐색을 종료한다.

ELSE IF 현재 지형의 높이가 더 높다면 경사로의 길이 L만큼 뒤에 위치한 지형을 시작으로 경사로를 놓을 수 있는지 검사한다. 경사로를 놓을 수 없다면 탐색을 종료한다.

 

추가로, 이미 경사로를 설치한 지형에 중복으로 설치할 수 없으므로 경사로 설치 여부를 저장하는 배열을 통해 중복 설치를 방지하였다.

---

#include <iostream>
using namespace std;

class Map {
private:
	int N;
	int arr[101][101];

public:
	Map() : N(0) {}
	Map(int _N) : N(_N) {}

	void setTopography() {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				cin >> arr[i][j];
	}

	int getMapSize() {
		return N;
	}

	int getTopographyHeight(int y, int x) {
		if (y < 0 || y >= N || x < 0 || x >= N)
			return 0;

		return arr[y][x];
	}
};

class Runway {
private:
	int L;

public:
	Runway() : L(0) {}
	Runway(int _L) : L(_L) {}

	int getRunwayLength() {
		return L;
	}
};

enum {
	RIGHT, DOWN
};

class Person {
private:
	Map map;
	Runway runway;

	int readMap(int y, int x) {
		return map.getTopographyHeight(y, x);
	}

	bool isLayRunway(int y, int x, int height, bool layRunway[][101], int state) {
		int L = runway.getRunwayLength();

		switch (state) {
		case RIGHT:
			for (int i = 0; i < L; i++) {
				int adjHeight = readMap(y, x + i);
				if (layRunway[y][x + i] || adjHeight == 0 || adjHeight != height - 1)
					return false;
				layRunway[y][x + i] = true;
			}
			return true;

		case DOWN:
			for (int i = 0; i < L; i++) {
				int adjHeight = readMap(y + i, x);
				if (layRunway[y + i][x] || adjHeight == 0 || adjHeight != height - 1)
					return false;
				layRunway[y + i][x] = true;
			}
			return true;
		}

		return false;
	}
public:
	Person(Map& _map, Runway& _runway) {
		this->map = _map;
		this->runway = _runway;
	}

	bool isCheckPath(int y, int x, int state) {
		int N = map.getMapSize();
		int L = runway.getRunwayLength();

		if (y >= N || x >= N) return false;

		bool layRunway[101][101] = { false };
		int lastHeight = readMap(y, x);

		switch (state) {
		case RIGHT:
			while (++x < N) {
				int height = readMap(y, x);
				if (lastHeight == height)
					continue;
				else if (lastHeight > height) {
					if (!isLayRunway(y, x, lastHeight, layRunway, RIGHT))
						return false;
					x += L - 1;
				}
				else {
					x -= L;
					if (!isLayRunway(y, x, height, layRunway, RIGHT))
						return false;
					x += L;
				}

				lastHeight = height;
			}
			return true;

		case DOWN:
			while (++y < N) {
				int height = readMap(y, x);
				if (lastHeight == height)
					continue;
				else if (lastHeight > height) {
					if (!isLayRunway(y, x, lastHeight, layRunway, DOWN))
						return false;
					y += L - 1;
				}
				else {
					y -= L;
					if (!isLayRunway(y, x, height, layRunway, DOWN))
						return false;
					y += L;
				}

				lastHeight = height;
			}
			return true;
		}

		return false;
	}
};

void printAllPath(Map& map, Runway& runway) {
	Person person(map, runway);
	int pathCnt = 0;

	for (int y = 0; y < 100; y++)
		if (person.isCheckPath(y, 0, RIGHT)) {
			pathCnt++;
		}

	for (int x = 0; x < 100; x++)
		if (person.isCheckPath(0, x, DOWN)) {
			pathCnt++;
		}

	cout << pathCnt << endl;
}

int main(void) {
	int N, L;
	cin >> N >> L;

	Map map(N);
	Runway runway(L);

	map.setTopography();
	printAllPath(map, runway);

	return 0;
}