[백준 - Java] 14890번 : 경사로

문제

www.acmicpc.net/problem/14890

14890번: 경사로

설명

문제의 조건대로 구현하면 되는 문제이다.

하지만 조건을 이것저것 맞추다 보니 빼먹기도 하고, 경사로가 꼬이기도 해서 시간이 꽤나 걸렸던 문제다ㅠㅠ

 

* 경사로를 놓는 조건

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다.

또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다.

경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며,

아래와 같은 조건을 만족해야한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

* 주의해야 할 점 

- 행의 길, 열의 길 둘 다 고려해주어야 한다. 따라서 각각의 행과 열을 한 줄씩 배열로 만들어 조건을 검증했다.

 

- 경사로는 낮은 칸에 놓고, 높이차가 1이다.

따라서 2, 3과 같이 오름차순으로 높이차가 1이 나는지, 3, 2와 같이 내림차순으로 높이차가 1인지를 구별해주어야 한다.

오름차순으로 높이차가 1이 난다면 현재 칸 이전의 칸에 경사로를 놓을 수 있는지 확인하고,

내림차순으로 높이차가 1이 난다면 현재 칸부터 이후의 칸에 경사로를 놓을 수 있는지를 확인한다.

 

- 높이가 같은 경우는 신경 쓸 필요가 없고, 높이차가 1보다 큰 경우는 무조건 길을 지나갈 수 없다. 실패임.

전체 코드

높이차가 1 나는 경우를 구현하는 부분이 가장 오래 걸렸다.

전체 코드는 코드 최적화를 했지만, 처음에 높이차가 1 나는 경우에 대한 비효율적인 코드를 첨부한다. (앞으로 더 잘 생각하란 의미)

else if(arr[i] - arr[i-1] == 1) { // 오름차순으로 높이차 1인 경우  
	int j = i-1; // 현재 i칸 이전의 칸들 검사 
	int cnt = 0;

	// 범위를 벗어나지 않고, 높이가 같으며, 경사로가 없는 곳이고, L칸이 연속되지 않을 때까지 검사 
	while(j >= 0 && arr[j] == arr[i]-1 && !visited[j] && cnt < L ) {
		cnt++;
		j--;
	}

	if(cnt < L) {  // L칸이 연속되지 않는 경우 실패 
		return false;
	} else {
		// L칸이 연속되는 경우, j인덱스를 거슬러 올라오며 경사로 놓음 
		while(cnt != 0) {
			visited[j+1] = true;
			j++;
			cnt--;
		}
	}
}

////

else if(arr[i] - arr[i-1] == 1) { // 오름차순으로 높이차 1인 경우  
	for(int j = i-1; j >= i-L; j--) { // 현재 i칸 이전의 칸들 L만큼 검사 
		// 범위를 벗어나고, 높이가 다르고, 경사로가 있는 곳이라면 실패 
		if(j < 0 || arr[j] != arr[i]-1 || visited[j]) {
			return false;
		} 
		visited[j] = true;
	}
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static int N, L;

	public static void main(String[] args) 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());

		int[][] 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 ans = 0;
		
		// 행길, 열길로 나누어 지나갈 수 있는지 검사 
		int[] col = new int[N];
		int[] row = new int[N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				col[j] = map[i][j];
				row[j] = map[j][i];
			}
			
			// 지나갈 수 있다면 +1 
			if(solve(col)) ans++; // 행 길 검사 
			
			if(solve(row)) ans++; // 열 길 검사 
		}

		System.out.println(ans);
	}
	
	public static boolean solve(int[] arr) {
		boolean[] visited = new boolean[N]; // 경사로를 놓았는지 안 놓았는지 판별하기 위한 배열 
		
		for(int i = 1; i < N; i++) {
			if(arr[i] == arr[i-1]) { // 높이가 같으면 pass 
				continue;
			} else if(arr[i] - arr[i-1] == 1) { // 오름차순으로 높이차 1인 경우  
				for(int j = i-1; j >= i-L; j--) { // 현재 i칸 이전의 칸들 L만큼 검사 
					// 범위를 벗어나고, 높이가 다르고, 경사로가 있는 곳이라면 실패 
					if(j < 0 || arr[j] != arr[i]-1 || visited[j]) {
						return false;
					} 
					visited[j] = true;
				}
			} else if(arr[i] - arr[i-1] == -1) { // 내림차순으로 높이차 1인 경우 
				for(int j = i; j < i+L; j++) { // 현재 i칸 포함 이후의 칸들 L만큼 검사 
					// 범위를 벗어나고, 높이가 다르고, 경사로가 있는 곳이라면 실패 
					if(j >= N || arr[j] != arr[i] || visited[j]) {
						return false;
					} 
					visited[j] = true;
				}
			} else { // 1보다 큰 높이차라면 실패 
				return false;
			}
		}
		
		return true;
	}

}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2314890/src/Main.java

KwonMinha/BOJ