[백준] code.plus(시뮬레이션과 구현,JAVA)14890번, 경사로

문제 링크

14890번: 경사로

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 경사로는 높이의 차이가 1인 경우에만 놓을 수 있습니다.

2. 같은 높이가 L개가 연속되어야 경사로를 설치할 수 있다.

3. 각 행, 열마다 경사로를 놓고 이동할 수 있는 개수를 결과로 출력해야 한다.

 

이 문제에서 경사로를 놓는 것을 가장 중심적으로 두고 진행해야 합니다.

 

경사로를 놓고 높이가 큰 길로 올라가려면 같은 높이의 길이 L개가 존재해야 하기 때문에 길을 지날 때마다 같은 높이의 길이 몇 개가 있는지 확인합니다.

 

경사로를 놓고 높이가 낮은 길로 올라가려면 내려가려는 길의 다음 연속적인 길들이 같은 높이의 L개가 존재하면 가능합니다.

 

예제입력 1에 대입해보면

L = 2

1번째 열일 때

높이(↓)	같은 높이 연속된 개수
3	1
2	1
2	2
1	1
1	2
1	1

위에서 아래로 내려갈 때 높이 3의 길에서 높이 2의 길로 경사로를 놓을 수 있는지 확인하면

 

3 -> 2

내려가려는 길(2)이 같은 높이로 L(2)만큼 연속되기 때문에 경사로를 놓을 수 있습니다.

 

2 -> 1

내려가려는 길(1)이 같은 높이로 L(2)만큼 연속되기 때문에 경사로를 놓을 수 있습니다.

 

마지막 길(1)이 연속된 개수가 1이 되는 것은 앞에 연속된 높이 1인 길에는 경사로를 설치했기 때문입니다.

 

결과적으로 경사로를 설치하면 3 -> 1로 이동할 수 있기 때문에 지나갈 수 있는 길입니다.

 

4번째 행일 때

높이	1	1	1	2	2	2
연속된 개수	1	2	3	1	2	3

 

1 -> 2

올라가려고 할 때 같은 높이의 길이 L(2)보다 큰 3이 존재하기 때문에 경사로를 놓고 이동할 수 있습니다.

 

더 이상 경사로를 놓지 않고도 지나갈 수 있기 때문에 지나갈 수 있는 길입니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값을 받아서 저장합니다.

2. 해당 길이 높이가 1 차이나는 길로 올라갈 때와 내려갈 때를 구분하여 경사로를 놓을 수 있는지 확인합니다.

3. 경사로를 놓으면서 지나갈 수 있는 길이면 결과값 + 1을 진행합니다.

4. 모든 행과 열의 길이 지나갈 수 있는지 확인한 뒤 결과적으로 지나갈 수 있는 길의 개수를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 지도의 값들을 나누어 map에 저장하였습니다.
• 각 행과 열의 길마다 지날 수 있는 길인지 확인하는 wayCheck함수를 호출하는 cal함수를 실행하였습니다.
• BufferedWriter에 지나갈 수 있는 길의 개수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는  for문을 통해서 각 행과 열에 대하여 wayCheck 함수를 호출하였습니다. 
• wayCheck함수는 같은 높이의 길일 때 연속된 길의 개수를 +1합니다.
• wayCheck함수는 높은 높이의 길일 때 현재 연속된 길의 수를 확인하여 경사로를 놓일 수 있다면 지나간다.
• wayCheck함수는 낮은 높이의 길일 때 내려가려는 길이 L번 연속되는지 확인하고 경사로를 놓을 수 있으면 지나간다.

import java.util.*;
import java.io.*;
public class Main{
	static int N,L;
	static int[][] map;		//지도값 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장 및 배열 초기화
    	N = Integer.parseInt(st.nextToken());
    	L = Integer.parseInt(st.nextToken());
    	map = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	int result = cal();		//지나갈 수 있는 길 개수 구하는 함수 실행 및 결과 저장
    	bw.write(result + "\n");		//개수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //각 행과 열에 대한 지나갈 수 있는 길 확인하도록 호출하는 함수
    static int cal() {
    	int count = 0;
    	for(int i=0;i<N;i++) {
    		if(wayCheck(i, 0, map[i][0], 1, true))
    				count++;
    		if(wayCheck(0, i, map[0][i], 1, false))
    				count++;
    	}
    	return count;
    }
    //해당 길이 지나갈 수 있는지 확인하는 함수
    static boolean wayCheck(int row, int col, int cur, int check,boolean rowColCheck) {   	
    	if(rowColCheck)	//행 형태의 길이면
    		col++;
    	else		//열 형태의 길이면
    		row++;
    	
    	if(row==N || col == N) {	//지나갈 수 있는 길이면
    		return true;
    	}
    	
    	if(cur == map[row][col]) {		//같은 높이일 때
    		return wayCheck(row, col, cur, check+1,rowColCheck);
    	
    	}else if(cur == map[row][col]-1 && check>=L) {	//높은 높이일 때
    		return wayCheck(row, col, map[row][col], 1,rowColCheck);
    	
    	}else if(cur == map[row][col]+1) {		//낮은 높이일 때
    		cur = map[row][col];
            //내려가려는 길이 L개 연속되는지 확인
    		if(rowColCheck) {		//행 기준
    			if(col+L-1<N) {
    				boolean c = true;
    				for(int i=col;i<col+L;i++) {
    					if(cur!=map[row][i]) {
    						c = false;
    						break;
    					}
    				}
    				if(c)		//연속 될 시 경사로를 놓고 내려간다.
    					return wayCheck(row, col+L-1,map[row][col], 0, rowColCheck);
    			}
    		}else {		//열 기준
    			if(row+L-1<N) {	//내려가려는 길이 L개 연속되는지 확인
    				boolean c = true;
    				for(int i=row;i<row+L;i++) {
    					if(cur!=map[i][col]) {
    						c = false;
    						break;
    					}
    				}
    				if(c)		//연속 될 시 경사로를 놓고 내려간다.
    					return wayCheck(row+L-1, col,map[row][col], 0, rowColCheck);
    			}
    		}
    	}
    	return false;		//지나갈 수 없는 길일 때
    }
}