[백준][14890] 경사로

이 포스트는 백준 사이트의 경사로 문제 풀이입니다.

문제

해결 과정

N x N 크기의 지도에 각 칸의 높이가 주어질 때, 지나갈 수 있는 길 의 개수를 출력하는 문제입니다.
문제의 입력 조건에서 N 의 범위가 \(2 <= N <= 100\) 이므로 계단 방향 에 따른 순차탐색으로 풀 수 있었습니다.

우선 가로 방향으로 통과하는 길을 확인하려면 다음과 같은 조건을 만족해야 합니다.

1. 인접한 칸의 높이 차이는 1이하만 가능하다.
2. 높이 차이가 1 이고 경사로를 놓을 수 있는 공간 L 이 충분할 때, 경사로를 놓을 수 있다.

위 두 조건을 충족하면서 가로 방향 길을 확인하는 의사코드는 아래와 같습니다.

can_way_cnt = 0

for(row) {
    can_way = true
    for(col) {
        check_height_gap()
        
        if(height_gap >= 2) {
            can_way = false
            break
        }
    }

    if(can_way) {
        can_way_cnt += 1
    }
}

이 의사코드의 과정을 그대로 세로 방향에서 사용하면 정답 코드를 구현할 수 있습니다.

코드 구현

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N, L;
vector<vector<int>> board;

void input();
void solve();
bool can_make_steps(int start_row, int start_col, int end_row, int end_col);

int main() {
	input();
	solve();
	return 0;
}

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> L;

	board.assign(N, vector<int>(N, 0));
	for(int row = 0; row < N; ++row) {
		for(int col = 0; col < N; ++col) {
			cin >> board[row][col];
		}
	}
}

void solve() {
	int way_count = 0;

	for(int row = 0; row < N; ++row) {
		bool is_normal_way = true;
		int before_road_cnt = 1;
		for(int col = 0; col < N - 1; ++col) {
			int gap = abs(board[row][col] - board[row][col + 1]);
			if(gap > 1) {
				is_normal_way = false;
				break;
			} else if(gap == 0) {
				before_road_cnt += 1;
				continue;
			}

			if(board[row][col] > board[row][col + 1]) {
				if(can_make_steps(row, col + 1, row, col + L)) {
					col += L - 1;
					before_road_cnt = 0;
				} else {
					is_normal_way = false;
					break;
				}
			}
			else if(board[row][col] < board[row][col + 1]) {
 				if(before_road_cnt >= L) {
					before_road_cnt = 1;
				} else {
					is_normal_way = false;
					break;
				}
			}
		}

		if(is_normal_way) {
			way_count += 1;
		}
	}

	for(int col = 0; col < N; ++col) {
		bool is_normal_way = true;
		int before_road_cnt = 1;
		for(int row = 0; row < N - 1; ++row) {
			int gap = abs(board[row][col] - board[row + 1][col]);
			if(gap > 1) {
				is_normal_way = false;
				break;
			} else if(gap == 0) {
				before_road_cnt += 1;
				continue;
			}

			if(board[row][col] > board[row + 1][col]) {
				if(can_make_steps(row + 1, col, row + L, col)) {
					row += (L - 1);
					before_road_cnt = 0;
				} else {
					is_normal_way = false;
					break;
				}
			}
			else if(board[row][col] < board[row + 1][col]) {
 				if(before_road_cnt >= L) {
					before_road_cnt = 1;
				} else {
					is_normal_way = false;
					break;
				}
			}
		}
		if(is_normal_way) {
			way_count += 1;
		}
	}

	printf("%d", way_count);
}

bool can_make_steps(int start_row, int start_col, int end_row, int end_col) {
	if(start_row < 0 || start_row >= N || start_col < 0 || start_col >= N
	|| end_row < 0 || end_row >= N || end_col < 0 || end_col >= N)
		return false;

	int ground_height = board[start_row][start_col];
	if(start_row == end_row) {
		for(; start_col <= end_col; ++start_col) {
			if(ground_height != board[start_row][start_col]) {
				return false;
			}
		}
	} else if(start_col == end_col) {
		for(; start_row <= end_row; ++start_row) {
			if(ground_height != board[start_row][start_col]) {
				return false;
			}
		}
	}
	
	return true;
}

실행 결과