| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 |
- #시뮬레이션 #미생물 격리
- #dfs
- #BFS노필요.. #홈방범서비스
- #시뮬레이션
- #시뮬레이션 #dfs
- BFS
- #주사위 굴리기 #시뮬레이션
- #최단거리 #최소거리
- 정보처리기사 실기
- #dfs #완전탐색
- #recursion #strcmp #deque
- SW개발 테스트
- 취업준비생
- #pair배열
- #시뮬레이션 #recursion
- 실기
- #부분집합 #dfs
- #bfs
- 19년 3회
- bruteforce #DFS #완탐
- #DFS #BFS #라인
- #에라토스테네스의채 #소수판별
- 2019년10월
- #DFS #백트래킹
- #dfs #벽돌깨기 #swea
- #백준 #알고리즘 #SWEA #핀볼게임
- Today
- Total
Hokusai
[4] [모의 SW 역량테스트] 활주로 건설 본문
4014. [모의 SW 역량테스트] 활주로 건설
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
[Fig. 1] 과 같은 N * N 크기의 절벽지대에 활주로를 건설하려고 한다.
각 셀의 숫자는 그 지형의 높이를 의미한다.
활주로를 [Fig. 2] 와 같이 가로 또는 세로 방향으로 건설할 수 있는 가능성을 확인하려고 한다.
활주로는 높이가 동일한 구간에서 건설이 가능하다.
높이가 다른 구간의 경우 활주로가 끊어지기 때문에 [Fig. 3] 과 같은 경사로를 설치해야만 활주로를 건설 할 수 있다.
경사로는 길이가 X 이고, 높이는 1 이다.
경사로는 높이 차이가 1 이고 낮은 지형의 높이가 동일하게 경사로의 길이만큼 연속되는 곳에 설치 할 수 있다.
예를 들어 [Fig. 4] 는 길이가 2 이고 높이가 1 인 경사로를 설치하는 예를 보여준다.
경사로의 길이 X 와 절벽지대의 높이 정보가 주어질 때,
활주로를 건설할 수 있는 경우의 수를 계산하는 프로그램을 작성하라.
[예시]
지도의 한 변의 크기 N 이 6, 경사로의 길이 X 가 2 일 때,
[Fig. 5] 와 같이 지형의 높이가 주어진 경우를 생각해 보자.
[Fig. 5] 의 지형 중 [ 3, 3, 3, 2, 1, 1 ] 의 경우 [Fig. 6] 과 같이 높이 2 인 구간이 경사로 길이보다 짧아서 활주로를 설치 할 수 없다.
[ 3, 3, 3, 2, 2, 1 ] 의 지형은 [Fig. 7] 과 같이 경사로를 지형 밖까지 설치해야 되기 때문에 활주로를 설치할 수 없다.
[ 2, 2, 3, 2, 2, 2 ] 지형과 [ 3, 3, 3, 2, 2, 2 ] 지형의 경우 아래 [Fig. 8-1], [Fig. 8-2] 와 같이 경사로를 설치하여 활주로를 건설할 수 있다.
[Fig. 5] 와 같은 지형에 활주로를 건설하는 방법은
아래 [Fig. 9] 와 같이 총 7 가지 ( 가로 방향 3 가지, 세로 방향 4 가지 ) 경우가 있다.
즉, 예제에 대한 정답은 7 이 된다
[제약사항]
1. 시간제한 : 최대 50 개 테스트 케이스를 모두 통과하는 데 C / C++ / Java 모두 3 초
2. N 의 크기는 6 이상 20 이하의 정수이다. ( 6 ≤ N ≤ 20 )
3. 경사로의 높이는 항상 1 이고, 길이 X 는 2 이상 4 이하의 정수이다. ( 2 ≤ X ≤ 4 )
4. 지형의 높이는 1 이상 6 이하의 정수이다.
5. 동일한 셀에 두 개 이상의 경사로를 겹쳐서 사용할 수 없다.
( 아래 [Fig. 10] 과 같은 경우는 경사로를 설치하여 활주로를 연결 할 수 없다. )
6. 경사로는 세워서 사용할 수 없다. ( [Fig. 11] 참고 )
[입력]
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,
그 다음 줄부터 T 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 크기인 N 과 경사로의 길이 X 가 주어진다.
다음 N 개의 줄에는 N * N 크기의 지형 정보가 주어진다.
[출력]
테스트 케이스 개수만큼 T 개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t" 로 시작하고 공백을 하나 둔 다음 정답을 출력한다. ( t 는 1 부터 시작하는 테스트 케이스의 번호이다. )
정답은 활주로를 건설할 수 있는 경우의 수이다.
=====================================================================================
[IDEA]
: BOJ의 활주로 문제와 같은 로직이다.
SWExpert에서는 답이 다르게 나오길래 뭐지.. 싶었는데 보니까 visited배열을 초기화 안해줬다..
설명은 BOJ 경사로 문제를 보면 된다. 코드는 text로 첨부한다.
[Codes]
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int N,L,arr[110][110],arr2[110][110],result;
int visited[110][110];
bool frontcheck(int row,int col);
bool backcheck(int row,int col);
void check(int idx);
int main(void)
{
int test;
cin>>test;
for(int t=1;t<=test;t++)
{
result = 0;
for(int i=1;i<=N;i++)
{
memset(arr[i],0,sizeof(arr[i]));
memset(arr2[i],0,sizeof(arr2[i]));
memset(visited[i],0,sizeof(visited[i])); //이걸 안해줘서 틀림;;
}
N = L = 0;
cin>>N>>L;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
cin>>arr[i][j];
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
arr2[i][j] = arr[j][i];
}
for(int i=1;i<=N;i++)
check(i);
for(int i=1;i<=N;i++)
memset(visited[i],0,sizeof(visited[i]));
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
arr[i][j] = arr2[i][j];
}
for(int i=1;i<=N;i++)
check(i);
cout<<"#"<<t<<' '<<result<<endl;
}
return 0;
}
bool frontcheck(int row,int col)
{
bool flag = true;
if(col+L>N)
return false;
else
{
for(int i=1;i<=L;i++)
{
if(abs(arr[row][col+i]-arr[row][col]) != 1)
{
flag = false;
break;
}
}
if(flag)
{
for(int i=1;i<=L;i++)
{
if(visited[row][col+i] == 1)
{
flag = false;
break;
}
}
}
if(!flag)
return false;
else
{
for(int i=1;i<=L;i++)
visited[row][col+i] = 1;
return true;
}
}
}
bool backcheck(int row,int col)
{
bool flag = true;
if(col-L<1)
return false;
else
{
for(int i=1;i<=L;i++)
{
if(abs(arr[row][col-i]-arr[row][col]) != 1)
{
flag = false;
break;
}
}
if(flag)
{
for(int i=1;i<=L;i++)
{
if(visited[row][col-i] == 1)
{
flag = false;
break;
}
}
}
if(!flag)
return false;
else
{
for(int i=1;i<=L;i++)
visited[row][col-i] = 1;
return true;
}
}
}
void check(int idx)
{
int state;
for(int i=1;i<=N-1;i++)
{
state = arr[idx][i+1];
if(arr[idx][i] != state)
{
if(abs(arr[idx][i]-state) > 1)
return;
else
{
if(arr[idx][i]>state)
{
if(!frontcheck(idx,i))
return;
}
else if(arr[idx][i]<state)
{
if(!backcheck(idx,i+1))
return;
}
}
}
}
result++;
}
'알고리즘( C++ ) > 2. SW Expert Academy' 카테고리의 다른 글
| [6] [모의 SW 역량테스트] 미생물 격리 (0) | 2019.01.28 |
|---|---|
| [5] [모의 SW 역량테스트] 특이한 자석 (0) | 2019.01.24 |
| [3] [모의 SW 역량테스트] 보호 필름 (0) | 2019.01.22 |
| [2] [모의 SW 역량테스트] 무선 충전 (0) | 2019.01.14 |
| [1] [모의 SW 역량테스트] 핀볼 게임 (1) | 2019.01.03 |
