BOJ14890_경사로

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

문제요약

1. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

2. 지나갈 수 있는 길이가 몇 개 있는지 알아 보는 문제

3. 길이란 한 행 또는 한 열 전부를 나타낸다 , 한쪽 끝에서 다른쪽 끝까지 니나가는 것을 의미한다

4. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다 , 또는 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다

5. 경사로는 높이가 항상 1 , 길이는 L 이다

6. 경사로는 낮은 칸과 높은 칸을 연결한다

(1) 경사로는 낮은 칸에 놓으며 , L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다

(2) 낮은 칸과 높은 칸의 높이 차이는 1 이어야 한다

(3) 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고 , L개의 칸이 연속되어 있어야 한다

7. N : 2 <= N <= 100 , L : 1 <= L <= N , 각 칸의 높이는 10보다 작거나 같은 자연수 이다

8. 지나갈 수 있는 길의 개수를 구하여라

문제issue

1. 경사로를 둘 수 있는가?

(1) 높이 차이가 1인가?

(2) 그 전에 경사로를 둔 곳이 아닌가? - visited 체크

(3) 낮은 곳이 L 만큼 있는가?

해결흐름

1. 행을 한번 검사하고 열을 한번 검사하면서 cnt를 카운터하는 방식으로 진행한다.

2. 길은 그냥 지나갈 수 있는 길 , 경사로를 두면 지나갈 수 있는 길 , 경사로를 둘 수 없어서 못 지나가는 길 이렇게 3가지로 나뉜다.

3. 행을 검사한다고 했을 때

(1) 그냥 지나갈 수 있는 길 : 열에 해당하는 인덱스만 증가시켜준다

(2) 경사로가 필요한 길은 두 가지이다. 차이가 1일 경우 , 차이가 -1일 경우

(3) 차이가 1일 경우는 다음부터 나올 L만큼의 숫자가 현재보다 낮은 곳의 숫자와 같은지 본다 

(4) 차이가 -1일 경우는 전에 나왔던 L만큼의 숫자가 현재보다 낮은 곳의 숫자와 같은지 본다

(5) 같으면 number_cnt를 카운터 해줘서 마지막에 L과 비교해준다 , L과 다를 경우 visited를 초기화 해준다

4. 행 검사를 끝내고 열 검사를 하기 전에 visited를 초기화 해준다

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][N];
        boolean[][] visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // start
        int cnt = 0;
        // 행 검사
        for (int i = 0; i < N; i++) {
            int idx = 0;
            while (true) {
                // 끝까지 갔다
                if (idx >= N - 1) {
                    cnt++;
                    break;
                }
                // 그냥 지나갈 수 있는 길이다
                if (idx + 1 < N && map[i][idx] - map[i][idx + 1] == 0) {
                    idx++;
                }
                // 경사로가 필요하다 , 다음부터 나올 L만큼을 봐야함
                else if (idx + 1 < N && map[i][idx] - map[i][idx + 1] == 1) {
                    int number = map[i][idx + 1];
                    int number_cnt = 0;
                    for (int j = idx + 1; j < idx + 1 + L; j++) {
                        if (j < N && number == map[i][j] && !visited[i][j]) {
                            number_cnt++;
                            visited[i][j] = true;
                        }
                    }
                    if (number_cnt >= L) {
                        idx++;
                    }
                    else {
                        visited = new boolean[N][N];
                        break;
                    }
                }
                // 경사로가 필요하다 , 전에 나온 L만큼을 봐야함
                else if (idx + 1 < N && map[i][idx] - map[i][idx + 1] == -1) {
                    int number = map[i][idx];
                    int number_cnt = 0;
                    for (int j = idx; j > idx - L; j--) {
                        if (j >= 0 && number == map[i][j] && !visited[i][j]) {
                            number_cnt++;
                            visited[i][j] = true;
                        }
                    }
                    if (number_cnt >= L) {
                        idx++;
                    }
                    else {
                        visited = new boolean[N][N];
                        break;
                    }
                }
                // 갈 수 없다
                else {
                    break;
                }
            }
        }
        visited = new boolean[N][N];
        // 열 검사
        for (int i = 0; i < N; i++) {
            int idx = 0;
            while (true) {
                // 끝까지 갔다
                if (idx >= N - 1) {
                    cnt++;
                    break;
                }
                // 그냥 지나갈 수 있는 길이다
                if (idx + 1 < N && map[idx][i] - map[idx + 1][i] == 0) {
                    idx++;
                }
                // 경사로가 필요하다 , 다음부터 나올 L만큼을 봐야함
                else if (idx + 1 < N && map[idx][i] - map[idx + 1][i] == 1) {
                    int number = map[idx + 1][i];
                    int number_cnt = 0;
                    for (int j = idx + 1; j < idx + 1 + L; j++) {
                        if (j < N && number == map[j][i] && !visited[j][i]) {
                            number_cnt++;
                            visited[j][i] = true;
                        }
                    }
                    if (number_cnt >= L) {
                        idx++;
                    }
                    else {
                        visited = new boolean[N][N];
                        break;
                    }
                }
                // 경사로가 필요하다 , 전에 나온 L만큼을 봐야함
                else if (idx + 1 < N && map[idx][i] - map[idx + 1][i] == -1) {
                    int number = map[idx][i];
                    int number_cnt = 0;
                    for (int j = idx; j > idx - L; j--) {
                        if (j >= 0 && number == map[j][i] && !visited[j][i]) {
                            number_cnt++;
                            visited[j][i] = true;
                        }
                    }
                    if (number_cnt >= L) {
                        idx++;
                    }
                    else {
                        visited = new boolean[N][N];
                        break;
                    }
                }
                // 갈 수 없다
                else {
                    break;
                }
            }
        }
        System.out.println(cnt);
    } // end of main
} // end of class