[백준 Java] 14890 경사로

문제 링크

https://www.acmicpc.net/problem/14890

 

풀이

SW Expert Academy에서 풀었던 문제이다. 활주로 건설과 같은 문제인데 그때에는 행과 열에 대해서 모두 조사하는 방식이었지만, 이번에는 맵 2개를 선언하여 하나의 맵은 90도 회전한 맵으로 저장하고 두 맵을 한 행씩 조사하는 로직으로 변경했다.

 

한 행을 검사할 때, 행의 첫번째 값과 카운트를 갱신해둔다.

두번째 요소부터 검사할때 첫번째 행의 값과 같다면 카운트를 증가시키고 넘어간다.

이전 값과 다를 때 차이가 1이 아니라면 이 행은 경사로를 세울 수 없어 false를 리턴한다.

이전값과의 차이가 1이라면 높이가 올라가는 경우, 아니라면 낮아지는 경우에 따라 경사로를 세울 수 있는 조건 확인을 다르게 한다.

높아지는 경우, L만큼 공간을 만들 수 있는지 확인하고 만들 수 없다면 false, 만들 수 있다면 cnt와 prev 값을 갱신한다.

낮아지는 경우, 지금 위치에서 L만큼 위치까지 전부 같은 값인지 확인한다. 다른 값이 있다면 false, 전부 같은 값이라면 경사로를 만들 수 있고, L만큼 만든 다음 위치로 인덱스와 cnt를 조절한다. 이때 이 곳은 경사로를 만들었기 때문에 cnt는 0으로 설정한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, L, res, map[][], map2[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        N = Integer.parseInt(tokens.nextToken());
        L = Integer.parseInt(tokens.nextToken());
        map = new int[N][N];
        map2 = new int[N][N]; //i,j위치 반전시킨 맵

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
                map2[j][i] = map[i][j];
            }
        }

        res = 0;

        //기본 맵 행 검사, 회전한 맵 행 검사
        for (int i = 0; i < N; i++) {
            if (checkRow(map[i])) {
                res++;
            }
            if(checkRow(map2[i])){
                res++;
            }
        }

        System.out.println(res);
    }

    private static boolean checkRow(int[] rows) {
        //높이가 달라졌을 때 경사로를 생성할 수 있는지 확인
        int prev = rows[0];
        int cnt = 1;
        for (int i = 1; i < N; i++) {
            if (prev == rows[i]) { //높이가 같은 경우 그냥 증가
                cnt++;
                continue;
            }
            //높이가 다를 때
            if (Math.abs(prev - rows[i]) != 1) {
                //높이 차이가 1이 아니라면 경사로 만들지 못함
                return false;
            }
            //높이 차이가 1일 때
            //높아지는 경우 -> L만큼 공간을 만들 수 있는지 확인
            if (rows[i] - prev == 1) {
                if (cnt >= L) {
                    //경사로 생성
                    cnt = 1;
                    prev = rows[i];
                } else {
                    return false;
                }
            } else {
                //낮아지는 경우
                boolean flag = true;
                for (int j = i + 1; j < i + L; j++) {
                    if (!(j < N && rows[j] == rows[i])) {
                        flag = false;
                        break;
                    }
                }
                if (!flag) {
                    return false;
                } else {
                    //만들 수 있는 경우 만들고 경사로 만든 인덱스 조정하기
                    cnt = 0;
                    i = i + L - 1;
                    prev = rows[i];
                }

            }

        }
        return true;
    }
}