이번에는 백준 14890번 경사로 문제를 풀어보았습니다.
문제를 처음 봤을 때 행과 열을 각각 확인하면서 경사로를 놓을 수 있는지만 판단하면 되는 문제라고 생각했습니다.
처음에는 경사로를 직접 표시하는 방법을 생각했지만, 현재까지 연속된 같은 높이의 칸 개수만 관리해도 모든 경우를 판단할 수 있다는 점을 이용하여 구현하였습니다.
행과 열의 로직이 완전히 동일하기 때문에 행과 열을 각각 배열로 만들어 같은 함수를 두 번 호출하도록 구현하였습니다.
문제 설명
각 행과 열에 대해 한쪽 끝에서 다른 끝까지 지나갈 수 있는지 확인해야 합니다.
높이 차이가 1인 경우에는 길이 L의 경사로를 놓을 수 있습니다.
경사로를 놓을 수 있는 조건을 모두 만족하는 길의 개수를 구하는 문제입니다.
풀이 아이디어
행과 열을 각각 하나의 길이라고 생각하였습니다.
현재까지 같은 높이가 연속된 개수를 cnt로 관리하면서 탐색을 진행하였습니다.
- 높이가 같다면 연속된 개수를 증가시킵니다.
- 오르막이라면 현재까지 연속된 칸의 개수가 L 이상인지 확인합니다.
- 내리막이라면 앞으로 L칸을 사용해야 하므로
cnt를 음수로 만들어 아직 경사로를 설치 중이라는 상태를 표현하였습니다.
행과 열의 로직이 동일하기 때문에 원본 배열과 전치 배열을 만들어 같은 함수를 두 번 수행하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int n,m;
int ret;
void calculate(int arr[101][101]) {
for (int i=0; i<n; i++) {
int cnt = 1;
int j;
for (j=0; j<n-1; j++) {
if (arr[i][j] == arr[i][j+1])
cnt++;
else if (arr[i][j] + 1 == arr[i][j+1] && cnt >= m)
cnt = 1;
else if (arr[i][j] - 1 == arr[i][j+1] && cnt >= 0)
cnt = -(m-1);
else
break;
}
if (j == n-1 && cnt >= 0)
ret++;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
int a[101][101], b[101][101];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
b[j][i] = a[i][j];
}
}
calculate(a);
calculate(b);
cout << ret << '\n';
return 0;
}풀이 흐름
- 지도를 입력받습니다.
- 전치 배열을 함께 생성합니다.
- 모든 행에 대해 경사로를 설치할 수 있는지 확인합니다.
- 모든 열에 대해서도 같은 함수를 수행합니다.
- 지나갈 수 있는 길의 개수를 출력합니다.
구현 포인트
1. 행과 열을 같은 함수로 처리
행과 열의 로직이 동일하기 때문에 전치 배열을 만들어 같은 함수를 사용하였습니다.
b[j][i] = a[i][j];이후
calculate(a);
calculate(b);를 호출하여 행과 열을 각각 검사하였습니다.
2. 같은 높이인 경우
현재 높이와 다음 높이가 같다면 연속된 칸의 개수를 증가시켰습니다.
if (arr[i][j] == arr[i][j+1])
cnt++;현재까지 같은 높이가 몇 칸 이어졌는지 관리하였습니다.
3. 오르막 처리
다음 칸이 현재 칸보다 1 높은 경우입니다.
else if (arr[i][j] + 1 == arr[i][j+1] && cnt >= m)
cnt = 1;현재까지 연속된 칸의 개수가 L 이상이라면 경사로를 놓을 수 있으므로 다시 연속 개수를 1부터 시작하였습니다.
4. 내리막 처리
다음 칸이 현재 칸보다 1 낮은 경우입니다.
else if (arr[i][j] - 1 == arr[i][j+1] && cnt >= 0)
cnt = -(m-1);내리막은 앞으로 L개의 같은 높이 칸이 더 필요합니다.
그래서 cnt를 음수로 만들어 아직 경사로를 설치 중이라는 상태를 표현하였습니다.
이후 같은 높이가 계속 나오면서 cnt가 증가하게 되고, 다시 0 이상이 되면 경사로 설치가 완료된 상태가 됩니다.
5. 지나갈 수 있는 길 확인
끝까지 탐색을 완료했고, 경사로 설치도 모두 끝난 경우에만 정답을 증가시켰습니다.
if (j == n-1 && cnt >= 0)
ret++;cnt가 음수라는 것은 아직 내리막 경사로가 완성되지 않았다는 의미이므로 지나갈 수 없는 길로 처리하였습니다.
