[백준 14890번 / java] 경사로

문제

14890번: 경사로 (acmicpc.net)

1. NxN인 지도에 적힌 높이를 보고 몇 개의 행과 열을 지나갈 수 있는지 출력

2-1. 길에 속한 모든 칸의 높이가 같아야 길을 지나갈 수 있다.

2-2. 길에 경사로를 놓아 길을 지나갈 수 있다.

3. 경사로는 겹치면 안 된다.

풀이

구현 문제였다. 삼성 기출은 빡구현인가.. 푸는 데 3시간정도 걸린 것 같다.

 

1. 경사로를 놓는 방법

• 경사로의 길이가 L로 주어졌을 때, 낮은 쪽 L개의 칸에 경사로를 둬야 한다.
  •  경사로를 둘 자리가 있는지 확인해야 함
• 탐색하는 방향 기준으로 높이 변화가 두 가지 있다.
  • 높->낮 : 오른쪽으로 L개의 칸에 경사로를 둬야 함
  • 낮->높 : 왼쪽으로 L개의 칸에 경사로를 둬야 함

2. 탐색 방법

• 0부터 N까지 한 줄의 행을 돌면서 현재 값과 다음 값을 비교한다.
  • 둘의 차이가 1 이상이면 그 행은 지나갈 수 없다고 판단한다.
    •   경사로의 높이는 항상 1이기 때문이다. 1 이상의 높이 차이는 이을 수 없다.
  • 둘의 차이가 1이고, 다음 값이 더 크면 '올라가는 경사로'를 놓는다.
    • 경사로를 놓는 데 성공한다면, 현재 검사 중인 행의 다음 인덱스를 계속 검사한다.
    • 경사로를 놓을 수 없다면, 그 행은 지나갈 수 없다고 판단한다.
  • 둘의 차이가 1이고, 이전 값이 더 크면 '내려가는 경사로'를 놓는다.
    • 경사로를 놓는 데 성공한다면, 현재 검사 중인 행의 다음 인덱스를 계속 검사한다.
    • 경사로를 놓을 수 없다면, 그 행은 지나갈 수 없다고 판단한다.
  • N까지 한 줄의 행을 끝까지 순회하는 데 성공했다면 count++하고, 다음 행으로 이동한다.

* 열도 동일하게 진행

* 경사로를 놓았다면 겹치지 않도록 하기 위해 check배열에 경사로를 놓은 자리를 true로 변경해준다.

* 행 검사할 때 놓은 경사로는 열 검사할 때 영향을 미치지 않는다. <- 문제에서는 언급되어있지 않지만 힌트에서 얻을 수 있는 정보이다.

 

 

코드

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

public class boj_14890 {
    static int N, L;
    static int[][] board;
    static int[] slope;
    static boolean[][] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        slope = new int[L];
        slope[L-1] = 1; // 0, 0, .. , 0, 1

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

        check = new boolean[N][N];
        int count = 0;
        for(int i=0; i<N; i++){
            if(isPossibleInColumn(i))
                count++;
        }

        for(int i=0; i<N; i++){
            Arrays.fill(check[i], false );
        }

        for(int i=0; i<N; i++){
            if(isPossibleInRow(i))
                count++;
        }
        bw.write(count+" ");
        bw.close();

    }
    static boolean isPossibleInColumn(int k){ //k행에 대해 지나갈 수 있을지 확인하는 함수
        for(int i=0; i<N-1; i++){
            if(board[k][i+1] - board[k][i] == 1){ //앞보다 뒤가 1 큰 수
                if(!putSlopeOnColumn(k, i, "up")) //경사로가 놓일 수 없다면 false 반환
                    return false;
            }
            if(board[k][i] - board[k][i+1] == 1) { //뒤보다 앞이 1 큰 수
                if(!putSlopeOnColumn(k, i, "down")) //경사로가 놓일 수 없다면 false 반환
                    return false;
            }
            if(Math.abs(board[k][i] - board[k][i+1]) > 1)
                return false;
        }
        return true;
    }

    static boolean isPossibleInRow(int k){ //k열에 대해 지나갈 수 있을지 확인하는 함수
        for(int i=0; i<N-1; i++){
            if(board[i+1][k] - board[i][k] == 1){ //앞보다 뒤가 1 큰 수
                if(!putSlopeOnRow(i, k, "up")) //경사로가 놓일 수 없다면 false 반환
                    return false;
            }
            if(board[i][k] - board[i+1][k] == 1) { //뒤보다 앞이 1 큰 수
                if(!putSlopeOnRow(i, k, "down")) //경사로가 놓일 수 없다면 false 반환
                    return false;
            }
            if(Math.abs(board[i][k] - board[i+1][k]) > 1)
                return false;
        }
        return true;
    }

    static boolean putSlopeOnColumn(int x, int y, String dir){
        //열
        //x행 y열, x행 y+1열에 1차이 단차가 생김


        if(dir.equals("up")){
            if(y+1 < L) //경사로를 y부터 왼쪽으로 놓음 //열의 현재 인덱스가 경사로 길이보다 짧아서 경사로를 놓을 수 없음
                return false;


            for(int i=0; i<L; i++){ //이미 경사로가 놓여있음
                if(check[x][y-i])
                    return false;
            }

            for(int i=0; i<L; i++){ //현재 인덱스 포함하여 왼쪽으로 L칸 확인하며 모두 같은 숫자인지 확인, 숫자가 다르면 경사로를 놓을 수 없음
                if(board[x][y-i] != board[x][y])
                    return false;
            }

            for(int i=0; i<L; i++){ //경사로 놓기
                check[x][y-i] = true;
            }
            return true;
        } else {
            if(N-(y+1) < L) //경사로를 y+1부터 오른쪽으로 놓음 //열의 현재 인덱스+1이 경사로 길이보다 짧아서 경사로를 놓을 수 없음
                return false;


            for(int i=0; i<L; i++){ //이미 경사로가 놓여있음
                if(check[x][y+1+i])
                    return false;
            }

            for(int i=0; i<L; i++){ //현재 인덱스+1 포함하여 오른쪽으로 L칸 확인하며 모두 같은 숫자인지 확인, 숫자가 다르면 경사로를 놓을 수 없음
                if(board[x][y+1+i] != board[x][y+1])
                    return false;
            }

            for(int i=0; i<L; i++){ //경사로 놓기
                check[x][y+1+i] = true;
            }
            return true;
        }
    }
    static boolean putSlopeOnRow(int x, int y, String dir){
        //행
        //x행 y열, x+1행 y열에 1차이 단차가 생김


        if(dir.equals("up")){
            if(x+1 < L) //경사로를 y부터 왼쪽으로 놓음 //열의 현재 인덱스가 경사로 길이보다 짧아서 경사로를 놓을 수 없음
                return false;


            for(int i=0; i<L; i++){ //이미 경사로가 놓여있음
                if(check[x-i][y])
                    return false;
            }
            
            for(int i=0; i<L; i++){ //현재 인덱스 포함하여 왼쪽으로 L칸 확인하며 모두 같은 숫자인지 확인, 숫자가 다르면 경사로를 놓을 수 없음
                if(board[x-i][y] != board[x][y])
                    return false;
            }

            for(int i=0; i<L; i++){ //경사로 놓기
                check[x-i][y] = true;
            }
            return true;
        } else {
            if(N-(x+1) < L) //경사로를 y+1부터 오른쪽으로 놓음 //열의 현재 인덱스+1이 경사로 길이보다 짧아서 경사로를 놓을 수 없음
                return false;


            for(int i=0; i<L; i++){ //이미 경사로가 놓여있음
                if(check[x+1+i][y])
                    return false;
            }

            for(int i=0; i<L; i++){ //현재 인덱스+1 포함하여 오른쪽으로 L칸 확인하며 모두 같은 숫자인지 확인, 숫자가 다르면 경사로를 놓을 수 없음
                if(board[x+1+i][y] != board[x+1][y])
                    return false;
            }

            for(int i=0; i<L; i++){ //경사로 놓기
                check[x+1+i][y] = true;
            }
            return true;
        }
    }


}

Note

• 테케 4가 틀리게 나와서 힌트를 자세히 읽어봤다.
• 테케 4의 경우를 유심히 보면, 열은 열대로, 행은 행대로 경사로를 놓을 수 있다는 것을 알 수 있다.
• 나는 열을 지나가기 위해 놓은 경사로를 그대로 두고 행을 지나갈 수 있는지 확인했기 때문에 틀린 답이 나온 것
• 모든 열을 먼저 검사한 후 check배열을 초기화하고 다시 모든 행을 검사하도록 변경하였다.

• 이미 경사로가 놓여있는지 확인할 때, 경사로의 길이만큼 확인해야 한다.

if(check[x][y]) //변경 전
	return false;


for(int i=0; i<L; i++){ //변경 후
                if(check[x][y-i])
                    return false;
            }

 

• 거의 9N%에서 틀렸다고 나와서 아래 반례를 실행해보니 9가 나왔다. 
• 두 계단의 높이 차이가 2 이상이면 경사로를 못 놓게 하는 부분에, 높이 차이에 절댓값을 씌워주니 정답처리되었다.

10 2
2 2 3 5 3 1 1 1 1 1 
2 2 3 5 3 1 1 1 1 1 
3 3 4 5 4 3 2 1 1 2 
3 3 4 5 4 3 2 1 1 2 
5 5 5 5 5 5 3 1 1 3 
4 4 4 5 5 5 4 3 3 3 
4 4 4 5 5 5 5 5 5 3 
4 4 4 4 4 5 5 5 5 3 
4 4 4 4 4 5 5 5 5 3 
5 5 4 4 4 5 5 5 5 4 
//정답 : 4