[백준] 14890 - 경사로 (JAVA)

개츠비·2023년 4월 7일

백준

목록 보기

58/84

소요시간 : 2시간 20분
문제 사이트 : 백준
문제 수준 : 골드 3
문제 유형 : 구현
다른 사람의 풀이를 참고 했는가 ? : X
한 번 풀었다가 다시 푸는 문제인가 ? : X
문제 링크 : https://www.acmicpc.net/problem/14890
푼 날짜 : 2023.04.08

1. 사용한 자료구조 & 알고리즘

구현.....!! 했다.

2. 사고과정

문제 솔직히 보는 순간 숨이 턱 막혔다.
어떻게 구현해야 할지 막막했다.
그래도 친절하게 힌트로 각각의 경우 어느 길이 가능한지 알려줬기에
내가 직접 어떻게 가능한건가 그려보기로 했다.

먼저 경사로를 놓는 조건을 생각해보기로 했다. 어떤 경우에 경사로를 놓아야 하는가 ?
먼저 경사로에는 2가지 종류가 있기에 각각 정의해야한다.

나는 다음과 같이 점점 짧아지는 경사로를 내려가는 경사로
점점 길어지는 경사로를 올라가는 경사로 로 정의했다.

내려가는 경사로가 설치되는 조건은 무엇일까 ?

(1) 이번 좌표가 이전 좌표보다 1 낮다.
(2) 이번좌표부터 L개의 좌표의 높이가 같다.
(3) 이번 좌표부터 L개의 좌표에 올라가는 경사로가 설치되어 있지 않아야한다.

이다.
그렇다면 올라가는 경사로는 ?

(1) 이번 좌표가 이전 좌표보다 1 높다.
(2) 이번 좌표부터 L개의 좌표의 높이가 같다.
(3) 이번 좌표부터 L개의 좌표에 내려가는 경사로가 설치되어 있지 않아야한다.

이 규칙을 찾아 냈다. 하지만 우리는 내려가는 경사로를 먼저 한 번 쭉 다 설치하고, 그 후에 올라가는 경사로를 설치한다면
내려가는 경사로가 설치되는 조건의 (3) 번을 무시할 수 있다.

이젠 경사로를 다 설치했다. 그렇다면 이제 시작 좌표부터 끝 좌표에 도달할 수 있는 조건은 무엇일까 ?
여기서는 3가지 조건 중 하나를 만족하면 된다.

이전 좌표의 높이와 현재 좌표의 높이가 같다.

현재 높이가 이전높이보다 1 낮고, 현재 높이에 내려가는 경사로가 있어야 한다.

현재 높이가 이전높이보다 1 크고, 이전 높이에 올라가는 경사로가 있어야 한다.

이 3가지 조건 중 하나라도 만족하지 못한다면, 이전 좌표에서 현재 좌표로 이동할 수 없고, 그 경우에는 count 를 세어 주지 않는다.

3. 풀이과정

편의상 가로 map, 세로 map 을 분리하여서 보지 않음. arr이라는 맵을 2배 길이로 선언하여 선언하고 가로, 세로를 한 번에 체크함.
각각의 경우마다 경사로를 놓는다. (앞서 말한 조건으로 )
경사로를 놓았다면 시작 좌표에서 끝 좌표까지 도달할 수 있는지 체크한다. 도달 한다면 할때마다 count를 증가
상세한 건 주석에!

4. 소스코드

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

public class Main{

	static int arr[][];
	static int L;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;

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

		int origin[][]=new int[N][N];
		arr=new int[N*2][N];

		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				origin[i][j]=Integer.parseInt(st.nextToken());
				arr[i][j]=origin[i][j];
			}
		}
		
		int idx=N;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				arr[idx][j] = origin[j][i];
			}
			idx++;
		}
		
		boolean slider[][];
		int count = 0;
		for(int i=0;i<arr.length;i++) {
			slider=new boolean[arr[0].length][2];

			//경사로를 놓음.
			putSlider(slider,i);

			boolean check=true;
			
			for(int j=1;j<arr[0].length;j++) {
				//이전 높이와 현재 높이가 같다면 continue
				//현재 높이가 이전높이보다 1 낮고, 현재 높이에 내려가는 경사로가 있다면 continue
				//현재 높이가 이전높이보다 1 크고, 이전 높이에 올라가는 경사로가 있다면 continue
				if(arr[i][j]==arr[i][j-1]) continue;
				if(arr[i][j]-arr[i][j-1]==-1&&slider[j][0]) continue;
				if(arr[i][j]-arr[i][j-1]==1&&slider[j-1][1]) continue;
				
				//이외의 경우에는 이전 좌표에서 현재 좌표로 이동할 수 없음. 
				check=false;
				break;
			}

			//시작 위치에서 끝 위치까지 도달 가능. count 증가
			if(check) count++;
			
		}
		
		System.out.println(count);


	}
	//경사로를 놓는 함수.
	public static void putSlider(boolean check[][],int idx) {

		//현재 위치에서 경사로를 놓을 수 있는지 check.
		//내려가는 경사로를 우선 설치
		for(int i=1;i<arr[0].length-L+1;i++) {
			
			//현재 위치가 이전 위치보다 낮다면
			if(arr[idx][i-1]-arr[idx][i]==1) {
				boolean put = true;
				int stan=arr[idx][i];

				//L개 만큼 높이가 같나 체크.
				for(int j=0;j<L;j++) 
					if(arr[idx][i+j]!=stan) put = false;

				//설치 가능하면 설치
				if(put) {
					for(int j=0;j<L;j++) 
						check[i+j][0] = true;
				}
			}
		}

		//올라가는 경사로를 설치
		for(int i=arr[0].length-1;i>=L;i--) {
			
			//현재 위치가 이전 위치보다 높다면
			if(arr[idx][i]-arr[idx][i-1]==1) {
				boolean put = true;
				int stan=arr[idx][i-1];

				//L개만큼 높이가 같나 체크.
				//내려가는 경사로가 이미 설치되어 있나 체크.
				for(int j=0;j<L;j++) {
					if(arr[idx][i-j-1]!=stan) put = false;
					if(check[i-j-1][0]) put = false;
				}

				//설치 가능하면 설치
				if(put) {
					for(int j=0;j<L;j++) 
						check[i-j-1][1] = true;
				}

			}
		}


	}


}