(c++)백준 14890번: 경사로

www.acmicpc.net/problem/14890

14890번: 경사로

[풀이]

문제에 있는 조건대로 구현하는 문제였다.

bfs를 응용하여 풀었다.

 

경사로 조건

1. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.

→지금까지 거쳐온 칸 수 저장, 칸 수 ≥ L이면 놓을 수 있다.

→낮아지는 경우에는 y + L번째 칸까지 같은 높이인지 확인

 

2. 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.

→(Map[x][ny] == Map[x][y]+1)인 경우와 (Map[x][y] == Map[x][ny]+1)인 경우

 

3. 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

→1번과 동일

 

※가로길과 세로길을 따로 구하여 지나갈 수 있는 길의 개수를 더해주기

 

 

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

struct State {
	int x, y;
	int cnt;
};

int N, L;
int Map[100][100];

//가로로 지나갈 수 있는 길의 개수
int Row() {
	int res = 0;
	queue<State>q;
	for (int i = 0; i < N; i++) {
		q.push({ i,0,1 });
	}
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		q.pop();
		//길을 다 지나갔으면
		if (y == N - 1) {
			res++;
			continue;
		}
		int ny = y + 1;
		//현재 칸하고 높이가 같으면
		if (Map[x][ny] == Map[x][y]) {
			q.push({ x,ny,cnt + 1 });
		}
		//현재 칸보다 1높고 경사로를 놓을 수 있으면
		else if (Map[x][ny] == Map[x][y] + 1 && cnt >= L) {
			q.push({ x,ny,1 });
		}
		//현재 칸보다 1낮을 경우
		else if (Map[x][ny] + 1 == Map[x][y]) {
			//범위를 벗어나지 않으면
			if (y + L < N) {
				bool flag = true;
				//모두 같은 높이인지 확인
				for (int i = 2; i <= L; i++) {
					if (Map[x][y + i] != Map[x][ny]) {
						flag = false;
						break;
					}
				}
				if (flag) {
					q.push({ x,y + L,0 });
				}
			}
		}
	}
	return res;
}

//세로로 지나갈 수 있는 길의 개수
int Col() {
	int res = 0;
	queue<State>q;
	for (int i = 0; i < N; i++) {
		q.push({ 0,i,1 });
	}
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		q.pop();
		//길을 다 지나갔으면
		if (x == N - 1) {
			res++;
			continue;
		}
		int nx = x + 1;
		//현재 칸하고 높이가 같으면
		if (Map[nx][y] == Map[x][y]) {
			q.push({ nx,y,cnt + 1 });
		}
		//현재 칸보다 1높고 경사로를 놓을 수 있으면
		else if (Map[nx][y] == Map[x][y] + 1 && cnt >= L) {
			q.push({ nx,y,1 });
		}
		//현재 칸보다 1낮을 경우
		else if (Map[nx][y] + 1 == Map[x][y]) {
			//범위를 벗어나지 않으면
			if (x + L < N) {
				bool flag = true;
				//모두 같은 높이인지 확인
				for (int i = 2; i <= L; i++) {
					if (Map[x+i][y] != Map[nx][y]) {
						flag = false;
						break;
					}
				}
				if (flag) {
					q.push({ x + L,y,0 });
				}
			}
		}
	}
	return res;
}

int main() {
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
		}
	}
	int r = Row();
	int c = Col();
	cout << r + c << '\n';
	return 0;
}