곽로그

[백준 14890, Java] 경사로 본문

알고리즘/백준

[백준 14890, Java] 경사로

일도이동 2020. 9. 17. 01:39
반응형

문제

www.acmicpc.net/problem/14890

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

문제이해

1) 이 문제를 이해하는데 가장 시간이 오래걸렸던 부분

 L= 2 이고 222333이 주어졌다고 했을때 이게 왜 길이 되는지 이해가 안갔다. 내가 이해한 것은 222갯수가 3이니까 3인 경사로를 만들어야하는데 주어진 조건은 2라서 길이 될 수 없다고 생각했다. 

 

2) 문제 독해!!

결국엔 문제를 얼마나 빨리, 정확하게 이해하는 게 관건인 것 같다. 문제를 푸는데 급급하지 말고 충분한 시간을 가지고서 문제를 정확히 이해한다음에 풀자.

 

3) 구체적으로 생각하기

문제 이해할 때는 구체적인 예 하나 먼저 생각

 

소스코드

1. 처음 버전

- 아래 코드의 문제는 map 하나를 행을 기준으로 순회하는 거 한번, 열을 기준으로 순회하는 거 한번 각각 따로 구현하는데, 비슷한 로직에 [r][c] 위치만 바꾼거라 쓸데 없이 장황하다 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N;
        int L;
        int pathCount = 0;

        String line;
        StringTokenizer st;

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

        map = new int[N][N];
        for(int r = 0; r<N; r++){
            line = br.readLine();
            st = new StringTokenizer(line," ");
            for(int c = 0; c<N; c++){
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        for(int r = 0; r <N; r++){
            int pathHeight = map[r][0];
            int plainPathCount = 1;
            boolean isPath= true;
            boolean isPlain = true;

            for(int c = 1; c<N; c++){
                int currentHeight = map[r][c];
                if(pathHeight == currentHeight){
                    plainPathCount++;
                }
                else if(pathHeight<currentHeight){
                    //오르막 경사
                    isPlain =false;
                    isPath = canMakeUpperSlope(plainPathCount,L);

                    if(!isPath) break;
                    pathHeight = currentHeight;
                    plainPathCount =1;
                }
                else{
                    //내리막 경사
                    isPlain = false;
                    isPath = canMakeLowerSlopeRow(r,c,pathHeight,L);

                    if(!isPath) break;
                    pathHeight = currentHeight;
                    plainPathCount =0;
                    c = c+L-1;
                }

            }
            //System.out.println("isPath:"+isPath+",isPlain:"+isPlain);
            if(isPath||isPlain) pathCount+=1;
        }


        for(int c = 0; c <N; c++){
            int pathHeight = map[0][c];
            int plainPathCount = 1;
            boolean isPath= true;
            boolean isPlain = true;

            for(int r = 1; r<N; r++){
                int currentHeight = map[r][c];
                if(pathHeight == currentHeight){
                    plainPathCount++;
                }
                else if(pathHeight<currentHeight){
                    //오르막 경사
                    isPlain =false;
                    isPath = canMakeUpperSlope(plainPathCount,L);

                    if(!isPath) break;
                    pathHeight = currentHeight;
                    plainPathCount =1;
                }
                else{
                    //내리막 경사
                    isPlain = false;
                    isPath = canMakeLowerSlopeColumn(r,c,pathHeight,L);

                    if(!isPath) break;
                    pathHeight = currentHeight;
                    plainPathCount =0;
                    r = r+L-1;
                }

            }

            if(isPath||isPlain) pathCount+=1;
        }

        bw.write(String.valueOf(pathCount));
        bw.flush();


    }
    public static int[][] map;
    public static boolean canMakeUpperSlope(int plainPathCount, int L){
        return plainPathCount>= L;
    }
    public static boolean canMakeLowerSlopeRow(int r, int c, int pathHeight, int L){
        int lowerHeight = map[r][c];
        if(pathHeight-lowerHeight!=1){
            return false;
        }
        else{
            int lowerPlainCount = 0;
            for(int lowerC = c; lowerC<map[r].length;lowerC++){
                if(lowerHeight == map[r][lowerC]){
                    lowerPlainCount+=1;
                }
                else{
                    break;
                }

            }

            if(lowerPlainCount>=L){
                return true;
            }
            else{
                return false;
            }
        }
    }
    public static boolean canMakeLowerSlopeColumn(int r, int c, int pathHeight, int L) {
        int lowerHeight = map[r][c];
        if (pathHeight - lowerHeight != 1) {
            return false;
        } else {
            int lowerPlainCount = 0;
            for (int lowerR = r; lowerR < map[r].length; lowerR++) {
                if (lowerHeight == map[lowerR][c]) {
                    lowerPlainCount += 1;
                } else {
                    break;
                }

            }

            if (lowerPlainCount >= L) {
                return true;
            } else {
                return false;
            }
        }
    }
}

 

 

 

2. 두번째 버전

- 행 기준 순회, 열 기준 순회 2번을 어떻게 1개로 할까가 문제였는데, 처음 map 을 입력받을 때 두가지 버전으로 입력을 받고 공통함수를 적용하면 된다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N;
        int L;
        
        int[][] mapRow;
        int[][] mapColumn;
        String line;
        StringTokenizer st;

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

        mapRow = new int[N][N];
        mapColumn = new int[N][N];
        for(int r = 0; r<N; r++){
            line = br.readLine();
            st = new StringTokenizer(line," ");
            for(int c = 0; c<N; c++){
                int value = Integer.parseInt(st.nextToken());
                mapRow[r][c] =value;
                mapColumn[c][r] =value;
            }
        }

        Slope slope = new Slope(N,L,mapColumn);
        slope.countPath();
        
        slope.setMap(mapRow);
        slope.countPath();
        
        bw.write(String.valueOf(slope.getPathCount()));
        bw.flush();
    }
}
class Slope {
    private int N ;
    private int L ;
    private int[][] map;
    private int pathCount;
    
    Slope(int N, int L, int[][] map){
        this.N = N;
        this.L = L;
        this.map = map;
        pathCount = 0;
    }
    
    public  void countPath(){
        for(int r = 0; r <N; r++){
            int pathHeight = map[r][0];
            int plainPathCount = 1;
            boolean isPath= true;
            boolean isPlain = true;

            for(int c = 1; c<N; c++){
                int currentHeight = map[r][c];
                if(pathHeight == currentHeight){
                    plainPathCount++;
                }
                else if(pathHeight<currentHeight){
                    //오르막 경사
                    isPlain =false;
                    isPath = canMakeUpperSlope(plainPathCount,L);

                    if(!isPath) break;
                    pathHeight = currentHeight;
                    plainPathCount =1;
                }
                else{
                    //내리막 경사
                    isPlain = false;
                    isPath = canMakeLowerSlope(r,c,pathHeight,L);

                    if(!isPath) break;
                    pathHeight = currentHeight;
                    plainPathCount =0;
                    c = c+L-1;
                }

            }
            //System.out.println("isPath:"+isPath+",isPlain:"+isPlain);
            if(isPath||isPlain) pathCount+=1;
        }
    }
    private  boolean canMakeLowerSlope(int r, int c, int pathHeight, int L){
        int lowerHeight = map[r][c];
        if(pathHeight-lowerHeight!=1){
            return false;
        }
        else{
            int lowerPlainCount = 0;
            for(int lowerC = c; lowerC<map[r].length;lowerC++){
                if(lowerHeight == map[r][lowerC]){
                    lowerPlainCount+=1;
                }
                else{
                    break;
                }

            }

            return lowerPlainCount >= L;
        }
    }

    private  boolean canMakeUpperSlope(int plainPathCount, int L){
        return plainPathCount>= L;
    }
    
    public void setMap(int[][] map){
        this.map=map;
    }
    public int getPathCount(){
        return pathCount;
    }
}

 

반응형
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

[백준 14502, Java] 연구소  (0) 2020.09.28
[백준 17144, Java] 미세먼지 안녕!  (0) 2020.09.17
[백준 14888, Java] 연산자 끼워넣기  (0) 2020.09.11
[백준 14501, Java] 퇴사  (0) 2020.09.08
[백준 9095, Java] 1,2,3 더하기  (0) 2020.09.07
'알고리즘/백준' Related Articles more
Comments