BOJ 14890

2020-05-06

위 문제는 백준 사이트의 알고리즘 14890 문제에 관한 설명입니다.

문제

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다.

길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.

다음과 같은 N=6인 경우 지도를 살펴보자.

<img src= “https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14890/1.png” height = 300px, width = 300px>

이때, 길은 총 2N개가 있으며, 아래와 같다.

<img src= “https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14890/2.png” height = 300px, width = 300px>

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

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

경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다.

경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

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

  • 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다. 아래와 같은 경우에는 경사로를 놓을 수 없다.

  • 경사로를 놓은 곳에 또 경사로를 놓는 경우
  • 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
  • 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
  • 경사로를 놓다가 범위를 벗어나는 경우 L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

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

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다.

둘째 줄부터 N개의 줄에 지도가 주어진다.

각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다

import java.util.*;

public class Main {
    static int N, L, answer;
    static int[][] map1, map2;
    static int[] line;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        L = scanner.nextInt();

        map1 = new int[N][N];
        map2 = new int[N][N];

        for(int i = 0; i < N; i++)
            for(int j = 0 ; j < N; j++)
                map1[i][j] = map2[j][i] = scanner.nextInt(); //map1과 map2는 전치행렬이라고 생각!
        for(int i = 0 ; i < N; i++)
        {
            checkMap(i,map1);
            checkMap(i,map2);
        }
        System.out.println(answer);
    }
    private static void checkMap(int index, int[][]map){
        line = new int[N];
        for(int i = 0 ; i < N-1; i++)//다음 것과 같지 않은 경우 체크
        {
            if(map[index][i] != map[index][i+1]){
                int gap = map[index][i] - map[index][i+1];
                if(gap != -1 && gap != 1) return; // 차이가 1보다 크면 X
                if(gap == -1)
                {
                    for(int j = 0 ; j < L; j++)//왼쪽에서 경사가 시작
                    {
                        if(i-j <0 || line[i-j] ==1) return;//범위를 넘어갈 때, 이미 설치된 적있는가
                        if(map[index][i] == map[index][i-j]) line[i-j] = 1; //설치
                        else return;
                    }
                }
                else
                {
                    for(int j = 1; j <= L; j++)//오른쪽에서 경사가 시작
                    {
                        if(i+j >=N || line[i+j] ==1) return;//범위를 넘어갈 때, 이미 설치된 적있는가
                        if(map[index][i] -1 == map[index][i+j]) line[i+j] = 1; //설치
                        else return;
                    }
                }
            }
        }
        answer++;
    }
}

설명은 주석으로 소스코드를 참고!

경사로