[SW Expert] 4014. [모의 SW 역량테스트] 활주로 건설

생각

주어진 조건에 맞게 활주로를 건설하여라.

처음 생각

index의 숫자 값을 temp 변수에 저장시키면서 가로 완전 탐색한 뒤 세로 완전 탐색을 생각하였다.

▶ 비교를 해나가면서 만족 조건을 따져줘야하기 때문에 완전탐색을 하였다.

다음 생각

현재 index의 숫자 값을 기준으로 +1, -1, 같은지, 그 외 의 조건을 나누었고, 그 외 조건은 활주로의 높이가 1이기 때문에 바로 break 문으로 빠져나가 다음 줄을 검사하였다.

다다음 생각

낮은 곳에서 +1되는 높은 곳으로 올라갈 때는 이전 까지 갯수를 센 것을 x값과 비교해서 바로 체크를 하면 됐는데, -1로 낮아지는 경우는 조금 난해했다.

▶ boolean형 변수인 flag를 하나 더 만들어서 낮은 조건을 따져야 하는건지 체크하였다.

다다다음 생각

여기까지하니 예제 조건은 거의다 맞았는데 1,2개 정도가 틀렸었다.

▶ 중복해서 활주로를 건설할 수 없다는 조건 때문에 2 2 1 1 1 2 2 요렇게 있을 때, 위의 조건들만 하면 x가 3일 경우 내려갈 때, 올라갈 때 다 만족하지만 실제로는 활주로가 중복 건설이 안되기 때문에 false 처리를 해주어야했다.

방안

1) 중복처리를 막기위해 이전 숫자와 같은 경우에서 개수 변수 cnt를 +1 시켜주고 flag2(내려왔을 경우)가 true 값이면 현 cnt와 x를 비교해서 x에 도달했으면 cnt를 0으로 초기화 시켜주었다.

▶올라갔을 경우는 바로 건설 가능 불가능이 체크되므로 내려갔을 경우만 체크하였다.

2) 가로처리와 세로처리는 인덱스만 교차시켜주면 되므로 복붙해서 i 와 j를 바꿔주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Solution {
    static int n,x;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            arr = new int[n][n];
            
            for(int j=0;j<n;j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=0;k<n;k++)
                    arr[j][k] = Integer.parseInt(st.nextToken());
            }
            
            sb.append("#"+i+" "+solve()+"\n");
        }
        System.out.print(sb);
    }
    
    private static int solve() {
        int result = 0;
        // 가로 탐색
        for(int i=0;i<n;i++) {
            int cnt = 0;
            int temp = arr[i][0];
            boolean flag = true;
            boolean flag2 = false;
            for(int j=0;j<n;j++) {
                if(temp==arr[i][j]) {
                    cnt++;
                    if(flag2&&cnt==x) {
                        cnt = 0;
                        flag2 = false;
                    }
                }else if(temp-1==arr[i][j]) {
                    // 앞 칸이 낮아졌다는건 앞쪽에 활주로를 체크해야함
                    if(flag2&&cnt<x) {
                        flag = false;
                        flag2 = false;
                        break;
                    }
                    cnt = 1;
                    flag2 = true;
                    temp = arr[i][j];
                }else if(temp+1==arr[i][j]) {
                    if(flag2&&cnt<x) {
                        flag = false;
                        flag2 = false;
                        break;
                    }
                    flag2 = false;
                    // 현 칸이 낮다는건 cnt를 기준으로 활주로를 체크해야함
                    if(cnt<x) {
                        flag = false;
                        break;
                    }
                    cnt = 1;
                    temp = arr[i][j];
                }else {
                    // 한 칸 차이가 아니면 활주로 불가
                    flag = false;
                    flag2 = false;
                    break;
                }
            }
            if(flag2) if(cnt<x) flag = false;
            if(flag) result++;
        }
        // 세로 탐색
        for(int i=0;i<n;i++) {
            int cnt = 0;
            int temp = arr[0][i];
            boolean flag = true;
            boolean flag2 = false;
            for(int j=0;j<n;j++) {
                if(temp==arr[j][i]) {
                    cnt++;
                    if(flag2&&cnt==x) {
                        cnt = 0;
                        flag2 = false;
                    }
                }else if(temp-1==arr[j][i]) {
                    // 앞 칸이 낮아졌다는건 앞쪽에 활주로를 체크해야함
                    if(flag2&&cnt<x) {
                        flag = false;
                        flag2 = false;
                        break;
                    }
                    cnt = 1;
                    flag2 = true;
                    temp = arr[j][i];
                }else if(temp+1==arr[j][i]) {
                    if(flag2&&cnt<x) {
                        flag = false;
                        flag2 = false;
                        break;
                    }
                    flag2 = false;
                    // 현 칸이 낮다는건 cnt를 기준으로 활주로를 체크해야함
                    if(cnt<x) {
                        flag = false;
                        break;
                    }
                    cnt = 1;
                    temp = arr[j][i];
                }else {
                    // 한 칸 차이가 아니면 활주로 불가
                    flag = false;
                    flag2 = false;
                    break;
                }
            }
            if(flag2) if(cnt<x) flag = false;
            if(flag) result++;
        }
        return result;
    }
}