[SW Expert] [모의 SW 역량테스트] 4014번 활주로 건설 (Java)

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;
    }
}