입력 : 지도 정보, 경사로 설치에 필요한 길의 길이
출력 : 지나갈 수 있는 길의 개수
풀이
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 |