[백준] 14890. 경사로

https://www.acmicpc.net/problem/14890

14890번: 경사로

---

이 문제를 조금 더 쉽게 풀기 위해서 다른 블로그를 통해서 아이디어를 얻을 수 있었습니다. 처음에 저는 내려가는 경사로가 아닌 올라가는 경사로만 만들면서 행과 열별로 탐색하려고 생각했는데, 그렇게 하면 반대방향에서도 고려해야 하므로 코드가 길어지고 복잡했습니다.

이 점을 해결하기 위해서

1. 올라가는 경사로만 행과 열별로 판단 하는 것이 아닌, 내려가는 경사로도 놓을 수 있다고 가정합니다. 먼저 올라가는 경사로를 놓을 때에는 같은 숫자가 있으면 len을 증가시켜주고 높이차이가 1이고 len 이 L 이상이면 경사로를 놓을 수 있기 때문에 경사로를 놓아줍니다. 현재 좌표가 다음 좌표보다 1 크게되면 내려가는 경사로를 놓을 수 있기 때문에 그 때부터 낮은 지점의 칸들이 L 만큼 있는지 확인해 주고 내려가는 경사로를 놓아 줍니다.

2. solving(int[][] map) 이라는 함수의 매개변수로 2차원 배열을 받는데, 여기에서 처음에 순차적으로 입력받은 map이라는 배열과 map의 행과 열을 바꾼 map2라는 배열을 매개변수로 넣어서 열단위로 계산하게 합니다. 그렇게 되면 하나의 함수로 행과 열을 계산하는 효과를 얻을 수 있기 때문에 두가지 경우를 더하면 정답입니다.

[ 문제 풀이 ]

1. map 을 입력받으면서 행과 열을 뒤집어서 map2를 입력받습니다. 정답을 출력할 때에는 solving(map) 과 solving(map2)를 더해서 출력합니다. 이렇게 하게 되면 행과 열을 모두 확인하면서 한쪽 끝에서 다른 끝까지 갈 수 있는지 구할 수 있습니다.

2. solving 함수는 크게 2가지 부분으로 나누어지게 됩니다.

(1) 낮은곳 -> 높은곳으로 갈 수 있는 경사로를 놓기 위해서 높이가 같은 연속된 길이를 len 으로 체크하고 len >= L 이면 경사로를 놓아주고 len을 초기화 시켜줍니다.

(2) 높은곳 -> 낮은곳으로 내려가는 경사로를 놓기 위해서는 map[i][j+1] - map[i][j] == 1 인지 판단하여 거기서 부터 다음 좌표가 같은 연속된 지점을 counting 해서 L 만큼 지나간 후에 경사로를 놓을 수 있으면 놓아주고, 현재 j가 열의 인덱스를 가지고 변하기 때문에 L-1 만큼 j의 길이를 바꿔주고 다시 반복문으로 올라가서 j를 1증가시켜주게되면 경사로를 놓은 다음 열부터 j를 변하게 할 수 있습니다.

---

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

// 14890 경사로

public class Main {

	static int N, L;
	static int[][] map, map2;

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

		StringTokenizer st;
		st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		map2 = 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());
				map2[j][i] = map[i][j];
			}
		}

		System.out.println(solving(map) + solving(map2));
	}
	
	public static int solving(int[][] map) {
		int answer = 0;
	
		Out : for (int i = 0; i < N; i++) {
			int len = 1;
			for (int j = 0; j < N - 1; j++) {

				// 길이가 같으면 연속된 길이를 표시하는 len 1 증가
				if (map[i][j] == map[i][j + 1]) len++;

				// 낮은곳 -> 높은곳
				else if (map[i][j + 1] - map[i][j] == 1) {
					if (len >= L) {
						len = 1;
					} else
						continue Out;

					// 높은곳 -> 낮은곳
				} else if (map[i][j] - map[i][j + 1] == 1) {
					
					if(j+1+L > N) continue Out;
					
					// 다음 칸부터 L만큼 같은 칸이 있는지 확인
					int value = map[i][j+1];
					for (int k = j + 1; k < j + 1 + L; k++) {
						if (map[i][k] != value) {
							continue Out;
						}
					}
					j += L-1;
					len = 0;
				} else {
					continue Out;
				}
			}
			answer++;
		}
		
		return answer;
	}
}