[백준 ]14890번 경사로

14890번: 경사로

• 지도의 각 칸에는 "높이"가 적혀져 있다.

• "길" 이란 "한 행 전부 " 또는 " 한 열 전부" 를 나타낸다 → 즉, 한쪽 끝에ㅓ, 다른쪽 끝까지 지나가는 것.

• 길을 지나갈 수 있기 위해 :

  1. "길에 속한 모든 칸 " 의 높이는 "같아야 " 한다.

  2. 또는, "경사로"를 높아, 지나갈 수 있는 길을 만들어야 한다.

  3. "경사로" 높이는 항상1, 길이는 L이다. 경사로의 개수는 매우 많다.

  4. "경사로"는 "낮은 칸" - 높은칸을 연결

     경사로 조건이 있는데, 글로는 이해가 어렵다.. 그림을 보자

     

     1. 경사로는 " 낮은 칸 " 에 놓아야 함. "낮은칸에 L개의 연속된 칸"에 경사로 바닥이 모두 접해야 함. (즉, { 경사로를 놓을 낮은 칸 } 의 높이는 모두 같아야 하며, L개의 칸이 연속되어 있어야 )
        1. 경사로를 놓다가, 범위를 벗어나면 안됨.
     2. 낮은 칸, 높은 칸 높이 차이는 1이어야 함.

문제 이해

• 행, 열로만 따로 생각하면 된다.
• 이건 전체탐색을 해야만 하는 것 같다. 2N 개의 행,열 에 대하여 탐색을 해야 한다.
• 먼저
  1. 모든 칸의 높이가 같은가
  2. 높이가 다른 지점 부터
     1. i와 i+1의 높이를 비교해 간다.
        1. h(i) < h(i+1) 인 경우라면 , i로부터 left로 L개가 h(i)와 높이가 같아야 한다.
           1. Out of index 이면 이 줄은 실패인거임.
           2. 높이가 서로 다르다면 실패인 거임.
        2. h(i) > h (i+1) 인 경우라면, i+1로부터 right로 L개가 h(i+1)과 높이가 같아야 한다.
           1. Out of index이면 이 줄은 실패인 거임.
           2. 높이가 서로 다르다면 실패인 거임.
     2. 위의 높이를 비교한 경우
        1. h(i) < h(i+1) 인 경우 였다면, i+1부터 쭉 다시 하면 된다.
        2. h(i) > h(i+1) 인 경우 였다면, i+1+L부터 쭉 다시 하면 된다.

💥💥 내가 고려하지 않은 것

💥💥 문제 이해가 매우 짜증났다. 삼성문제가 다 그렇지 뭐..

• 위의 경우를 고려하기 위해서 grad 라는 테이블을 추가했다.
• 즉, 경사가 필요해서 해당 위치를 살펴보는데, 해당 위치에 , 이미 경사가 놓여있다면, 해당 줄은 실패인 것이다.
• 이 때, row의 경사와, col의 경사를 따뤄줘야 한다. 왜냐하면 아래와 같은 경우,

1 1     2(g)
2 1(g)  1(g) <-- 이 부분이 겹치게 되고, 이미 경사가 있는것으로 인식되어 실패가 뜨게된다
1 1     1(g) 

• 따라서 3차원의 grad 테이블을 생성해주었다.

package cote;

import java.io.*;
import java.util.*;

public class Main {
    public static int n,l;
    public static int cnt=0;
    public static int[][] board;
    public static boolean[][][] grad;
    public static void Setting() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        board = new int[n][n];
        // 경사로를 따로...저장해야하나. row, col의 경사로를 따로 저장함.
        // row에서 경사로 만들어서, col에서 경사로 못만드는 것은 아니기 때문에.
        // 하지만 row에서 경사 만들어서, 그 row에서 경사로가 겹치게 되면 경사로를 만들수 없는 것이기 때문에 grad 테이블을 따로 생성
        
        grad = new boolean[2][n][n];
        for(int r =0;r<n;r++){
            st = new StringTokenizer(br.readLine());
            for (int c=0;c<n;c++){
                board[r][c]= Integer.parseInt(st.nextToken());
            }
        }
    }
    public static void solve(){
        // row 별로 해보기.
        boolean same;
        for(int r=0;r<n;r++){
            boolean succ = true;
            for(int c=0;c<n-1;c++){
                if(board[r][c]==board[r][c+1])continue;
                // i+1칸의 높이가 더 큰 경우
                else if(board[r][c]<board[r][c+1]){
                    // 1. 높이차이가 1보다 큰 경우 -> 실패
                    if(board[r][c+1]-board[r][c] >1) {succ=false; break;}
                    // 2. (out of range)l이 2인데 c가 0 이면 안됨. c가 1인 것은 가능함. c-l+1 이 0 이상이어야함
                    // 실패
                    if(c-l+1<0) {succ=false; break;}
                    same = true;
                    // 3. c부터 좌측으로 l개의 칸이 모두 같은 높이여야 한다.
                    for(int curc = c;curc>=c-l+1;curc--){

                        if(board[r][curc]==board[r][c] && grad[0][r][curc]==false) {
                            grad[0][r][curc]=true;
                            continue;
                        }
                        same =false;
                        break;
                    }
                    if(same==false) {succ=false; break;}
                    else{
                        // 성공한 경우 -> 다음 c는 c+1임.

                    }
                }
                // i칸의 높이가 더 큰 경우
                else{
                    //1. 높이차이가 1보다 큰 경우->실패
                    if(board[r][c]-board[r][c+1] >1) {succ=false; break;}
                    // 2. out of range : c+1 + l -1 < n 예를들어, c+1이 1 인데 l이 2,n이3이면 가능
                    if(c+1 + l -1 >= n ){succ=false; break;}
                    //3. c+1로부터 우측으로의 l개의 칸이 모두 같은 높이여야함.
                    same = true;
                    for(int curc =c+1;curc<=c+1+l-1;curc++){
                        if(board[r][curc]==board[r][c+1]&&grad[0][r][curc]==false) {
                            grad[0][r][curc]=true;
                            continue;
                        }
                        same =false;
                        break;
                    }
                    if(same==false) {succ=false; break;}
                    else{
                        // ,,,, 2 1 2  (l=1)
                        // 성공한 경우 -> 다음 c는 c+1+l부터해야 하므로
                        c = c+l-1; //c++를 하게 되니까
                    }
                }
            }
            if(succ==false)continue;
            // 모든 column이 통과하면 이 줄은 성공임
            //System.out.println("row "+r+" succees");
            cnt++;
        }
        
        // column : row들을 확인해야함
        for(int c=0;c<n;c++){
            boolean succ = true;
            for(int r=0;r<n-1;r++){
                //System.out.println("["+r+","+c+"]");
                if(board[r][c]==board[r+1][c])continue;
                    // i+1칸의 높이가 더 큰 경우
                else if(board[r][c]<board[r+1][c]){
                    // 1. 높이차이가 1보다 큰 경우 -> 실패
                    if(board[r+1][c]-board[r][c] >1) {succ=false; break;}
                    // 2. (out of range)l이 2인데 c가 0 이면 안됨. c가 1인 것은 가능함. c-l+1 이 0 이상이어야함
                    // 실패
                    if(r-l+1<0) {succ=false; break;}
                    same = true;
                    // 3. r부터 위로 l개의 칸이 모두 같은 높이여야 한다.
                    for(int curr=r;curr>=r-l+1;curr--){

                        if(board[curr][c]==board[r][c] && grad[1][curr][c]==false) {
                            grad[1][curr][c]=true;
                            continue;
                        }
                        same =false;
                        break;
                    }
                    if(same==false) {succ=false; break;}
                    else{
                        // 성공한 경우 -> 다음 c는 c+1임.
                    }
                }
                // i칸의 높이가 더 큰 경우
                else{
                    //1. 높이차이가 1보다 큰 경우->실패
                    if(board[r][c]-board[r+1][c] >1) {succ=false; break;}
                    // 2. out of range : c+1 + l -1 < n 예를들어, c+1이 1 인데 l이 2,n이3이면 가능
                    if(r+1 + l -1 >= n ){succ=false; break;}
                    //3. r+1로부터 아래로의 l개의 칸이 모두 같은 높이여야함.
                    same = true;
                    // curr = 0+1+1
                    // r+1+l -1 = 0 + 1+ 2 -1 = 2
                    for(int curr =r+1;curr<=r+1+l-1;curr++){
                        if(board[curr][c]==board[r+1][c]&&grad[1][curr][c]==false){
                            grad[1][curr][c]=true;
                            continue;
                        }
                        same =false;
                        break;
                    }
                    if(same==false) {succ=false; break;}
                    else{
                        // 성공한 경우 -> 다음 c는 c+1+l부터해야 하므로
                        r = r+l-1; //r++를 하게 되니까
                    }

                }
            }
            if(succ==false) continue;
            // 모든 row이 통과하면 이 줄은 성공임
            cnt++;
            //System.out.println("column "+ c+" success");
        }
    }

    public static void main(String[] args) throws IOException {
        Setting();
        solve();
        System.out.println(cnt);
    }
}

항상 시간을 조금이라도 줄이려면 변수 선언을 반복문 바깥에

• 위의 경우도 boolean same을 for loop 내부에서 선언했었는데 이 때는 시간 → 216ms가 나왔음
• boolean same을 가장 바깥의 for loop 바깥에 선언 —> 시간이 156ms로 줄었다.