본문 바로가기

개발/알고리즘

백준 알고리즘 14890

입력 : 지도 정보, 경사로 설치에 필요한 길의 길이

출력 : 지나갈 수 있는 길의 개수

 

풀이

1. 행과 열을 각각 처리하도록 구현. 지도의 길을 각각 조사해 지나갈 수 있는 길은 1을 리턴, 지나갈 수 없는 길은 0을 리턴했다.

2. 평지에서는 반복문을 continue, 높이가 2칸 이상이면 길을 만들 수 없기 때문에 0을 리턴했다.

3. check변수를 만들어 계단을 설치한 부분은 true로 하고 나머진 false로 만들었다. 길을 올라가야할 때는 지나온 길에 계단을 설치해야 하는데 이미 계단이 있다면 계단을 설치할 수 없기 때문이다.

 

#include <iostream>
using namespace std;

int board[101][101];
bool checkForRow[101][101];
bool checkForColumn[101][101];
int N, L;

int checkRow(int n){
	//n,i
	int beforeStair = board[n][0];
	for(int i=1; i<N; i++){
		if(board[n][i] > beforeStair + 1 || board[n][i] < beforeStair - 1)
			return 0;
		else if(board[n][i] == beforeStair)
			continue;
		else if(board[n][i] == beforeStair - 1){
			int j;
			for(j=0; j<L; j++){
				if(board[n][i+j] != beforeStair - 1)
					return 0;
				checkForRow[n][i+j] = true;
			}
			i += j-1;
			beforeStair -= 1;
		}
		else if(board[n][i] == beforeStair + 1){
			for(int j=1; j<=L; j++){
				if(i-j<0 || checkForRow[n][i-j] || board[n][i-j] != beforeStair)
					return 0;
				checkForRow[n][i-j] = true;
			}
			beforeStair+=1;
		}
	}
	
	return 1;
}

int checkColumn(int n){
	//i,n
	int beforeStair = board[0][n];
	for(int i=1; i<N; i++){
		if(board[i][n] > beforeStair+1 || board[i][n] < beforeStair-1)
			return 0;
		else if(board[i][n] == beforeStair)
			continue;
		else if(board[i][n] == beforeStair-1){
			int j;
			for(j=0; j<L; j++){
				if(board[i+j][n] != beforeStair-1 || i+j >= N)
					return 0;
				checkForColumn[i+j][n] = true;
			}
			i += j-1;
			beforeStair -= 1;
		}
		else if(board[i][n] == beforeStair + 1){
			for(int j=1; j<=L; j++){
				if(i-j<0 || checkForColumn[i-j][n] || board[i-j][n] != beforeStair)
					return 0;
				checkForColumn[i-j][n] = true;
			}
			beforeStair+=1;
		}
	}
	
	return 1;
}

int main() {
	int result = 0;
	
	cin>>N>>L;
	
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			cin>>board[i][j];
	
	for(int i=0; i<N; i++){
		result += checkRow(i);
		result += checkColumn(i);
	}
	
	cout<<result;
	
	return 0;
}

'개발 > 알고리즘' 카테고리의 다른 글

백준 알고리즘 15686  (0) 2019.04.12
백준 알고리즘 15685  (0) 2019.04.12
백준 알고리즘 14888  (0) 2019.02.28
백준 알고리즘 14503  (0) 2019.02.21
백준 알고리즘 14891  (0) 2019.02.20