[SW Expert Academy] 4014. 활주로 건설
Posted on
문제 :
Fig. 1] 과 같은 N * N 크기의 절벽지대에 활주로를 건설하려고 한다.
각 셀의 숫자는 그 지형의 높이를 의미한다.
활주로를 [Fig. 2] 와 같이 가로 또는 세로 방향으로 건설할 수 있는 가능성을 확인하려고 한다.
활주로는 높이가 동일한 구간에서 건설이 가능하다.
높이가 다른 구간의 경우 활주로가 끊어지기 때문에 [Fig. 3] 과 같은 경사로를 설치해야만 활주로를 건설 할 수 있다.
경사로는 길이가 X 이고, 높이는 1 이다.
경사로는 높이 차이가 1 이고 낮은 지형의 높이가 동일하게 경사로의 길이만큼 연속되는 곳에 설치 할 수 있다.
예를 들어 [Fig. 4] 는 길이가 2 이고 높이가 1 인 경사로를 설치하는 예를 보여준다.
경사로의 길이 X 와 절벽지대의 높이 정보가 주어질 때,
활주로를 건설할 수 있는 경우의 수를 계산하는 프로그램을 작성하라.
[ 제약 사항 ]
- 시간제한 : 최대 50 개 테스트 케이스를 모두 통과하는 데 C / C++ / Java 모두 3 초
- N 의 크기는 6 이상 20 이하의 정수이다. ( 6 ≤ N ≤ 20 )
- 경사로의 높이는 항상 1 이고, 길이 X 는 2 이상 4 이하의 정수이다. ( 2 ≤ X ≤ 4 )
- 지형의 높이는 1 이상 6 이하의 정수이다.
- 동일한 셀에 두 개 이상의 경사로를 겹쳐서 사용할 수 없다.
- 경사로는 세워서 사용할 수 없다.
입력 :
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,
그 다음 줄부터 T 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 크기인 N 과 경사로의 길이 X 가 주어진다.
다음 N 개의 줄에는 N * N 크기의 지형 정보가 주어진다.
출력 :
테스트 케이스 개수만큼 T 개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 “#t” 로 시작하고 공백을 하나 둔 다음 정답을 출력한다. ( t 는 1 부터 시작하는 테스트 케이스의 번호이다. )
정답은 활주로를 건설할 수 있는 경우의 수이다.
풀이 :
처음에는 DP 혹은 스택을 사용해야하는 문제가 아닐까 생각했지만 누적 평지 칸만 잘 세면 단순 구현 코드로 문제를 해결할 수 있었다.
단, 평지일 경우, 오르막 경로일경우, 내리막 경로일 경우, 높이 차이가 1 이상일 경우 등, 정확하게 조건을 잘 분석하는 과정이 필요하다.
문제에서는 flatcount(현재 누적 평지 개수)와 posdown(내리막일 경우, 앞에 있는 평지 개수를 판단해 경사로를 설치할 수 있을지 유무) 두 가지 속성 변수를 사용해서 각 경우의 수를 분석한다.
- 평지일 경우 : flatcount++
- 높이 차이가 1이상일 경우(오르막, 내리막 모두 포함) : 불가능한 경로이기에, 다음 행, 열 탐색 과정 진행
- 높이 차이가 1인 오르막 경로일 경우 : flatcount가 경사로 길이보다 크거나 같을 경우에 계속 진행 가능 => flatcount = 0, 현재높이++ 업데이트 필요
- 높이 차이가 1인 내리막 경로일 경우 : 반복문을 사용하여 이후 경로에 평지 개수가 몇 개인지 판단하고 경사로를 설치할 수 있는지 판단
삼성 SW 역량 문제는 풀어보면 구현에 가까운 문제가 많다. 따라서 어떤 알고리즘 문제든 그렇겠지만 삼성 SW 문제는 특히 처음 문제에 무작정 접근하기 보다는 조건을 확실히 파악하고 로직을 설계해 놓은 후 코딩에 들어가는 것이 훨씬 효율적인 것 같다.
코드 :
코드 보기/접기
#include<iostream>
using namespace std;
int map[20][20];
int testCase() {
int n, slopelength, runwaycnt = 0;
bool posdown;
cin >> n >> slopelength;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
for (int i = 0; i < n; i++) {
int flatcnt = 1, curh = map[i][0], j;
for (j = 1; j < n; j++) {
int nexth = map[i][j];
if (curh == nexth) flatcnt++;
else if (curh - nexth == -1) {
if (flatcnt >= slopelength) {
curh++;
flatcnt = 1;
} else break;
} else if (curh - nexth == 1) {
posdown = true;
for (int k = 1; k < slopelength; k++)
if ((j + k) >= n || nexth != map[i][j + k]) {
posdown = false;
break;
}
if (posdown) {
curh--;
flatcnt = 0;
j += slopelength - 1;
} else break;
} else break;
}
if (j >= n) runwaycnt++;
}
for (int i = 0; i < n; i++) {
int flatcnt = 1, curh = map[0][i], j;
for (j = 1; j < n; j++) {
int nexth = map[j][i];
if (curh == nexth) flatcnt++;
else if (curh - nexth == -1) {
if (flatcnt >= slopelength) {
curh++;
flatcnt = 1;
} else break;
} else if (curh - nexth == 1) {
posdown = true;
for (int k = 1; k < slopelength; k++)
if ((j + k) >= n || nexth != map[j + k][i]) {
posdown = false;
break;
}
if (posdown) {
curh--;
flatcnt = 0;
j += slopelength - 1;
} else break;
} else break;
}
if (j >= n) runwaycnt++;
}
return runwaycnt;
}
int main(int argc, char **argv) {
int test_case, T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case) {
cout << '#' << test_case << ' ' << testCase() << '\n';
}
return 0;
}