728x90
SW Expert [모의 SW 역량테스트] 4014번 활주로 건설 :
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH
딱히 알고리즘이랄 거 없이 문제에서 요구하는 조건만 만족하면 풀리는 문제이다.
요즘 dfs, bfs 등 여러 알고리즘을 사용해 문제를 풀다가 이런 문제를 보게 되니 뭔가 신선했다.
문제에서 요구하는 조건만 맞춰주면 풀리지만, 그 조건 맞추는 게 생각보다 까다롭다.
아래의 사진처럼 2차원 배열로 입력을 받으면 체크해야 할 부분은 각 행과 열, 총 2n개의 1차원 배열이 된다.
이를 간단하게 해주기 위해 입력을 받을 때 정상적인 배열과, 행과 열을 뒤바꾼 배열 총 2개로 저장했다.
이런 식으로 입력을 받으면 for문 1개로 두 배열의 행을 탐색하며 판단을 할 수 있다.
활주로를 건설할 수 있는지 없는지는 1차원 배열을 변수로 받는 isOk 함수에서 체크한다.
내려갈 때와 올라갈 때 두 파트로 나눠서 구현을 했으며, 안에 들어있는 로직은 비슷하다.
지형을 건설하면 1차원 boolean 배열인 check를 사용해서 체크를 해주었다.
따져야 하는 조건이 많아서 로직을 짤 때 고민을 많이 했다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int n, x;
private static int[][] map1, map2;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
map1 = new int[n][n];
map2 = new int[n][n];
for (int i = 0; i < n; i++) { // 입력
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int num = Integer.parseInt(st.nextToken());
map1[i][j] = num;
map2[j][i] = num;
}
}
int answer = solution();
System.out.println("#" + t + " " + answer);
}
}
private static int solution() {
int answer = 0;
for (int i = 0; i < n; i++) {
answer += isOk(map1[i]);
answer += isOk(map2[i]);
}
return answer;
}
private static int isOk(int[] array) { // 활주로 건설할 수 있으면 1, 없으면 0 리턴
boolean[] check = new boolean[n];
for (int i = 0; i < n - 1; i++) {
int prev = array[i];
int next = array[i + 1];
if (Math.abs(prev - next) > 1) return 0; // 2 이상 차이나면 return 0
if (check[i + 1] || prev == next) continue; // 평지거나 이미 지형이 있다면 패스
if (prev > next) { // 내려갈 때 : 3 3 2 2 1 1
for (int j = i + 1; j <= i + x; j++) { // 지형 설치
// n을 넘어가거나, 평지가 아니거나, 이미 지형이 있으면 return 0
if (j == n || array[j] != next || check[j]) return 0;
// 지형의 마지막은 값 그대로 가져가기 위한 if문
if (j != i + x) array[j] = next + 1;
check[j] = true; // 지형 설치 체크
}
} else { // 올라갈 때 : 1 1 2 2 3 3
for (int j = i; j > i - x; j--) {
if (j < 0 || array[j] != prev || check[j]) return 0;
if (j != i - x + 1) array[j] = prev + 1;
check[j] = true;
}
}
}
return 1;
}
}
728x90
'Algorithm > SW Expert Academy' 카테고리의 다른 글
[SW Expert] [모의 SW 역량테스트] 5644번 무선 충전 (Java) (0) | 2020.02.18 |
---|---|
[SW Expert] [모의 SW 역량테스트] 5648번 원자 소멸 시뮬레이션 (Java) (0) | 2020.02.18 |
[SW Expert] [모의 SW 역량테스트] 4013번 특이한 자석 (Java) (0) | 2020.02.17 |
[SW Expert] [모의 SW 역량테스트] 2112번 보호 필름 (Java) (0) | 2020.02.17 |
[SW Expert] [모의 SW 역량테스트] 2105번 디저트 카페 (Java) (0) | 2020.02.16 |