[코드트리] 보도블럭

문제

오르막과 내리막을 올라가거나 내려갈 수 있게 경사로를 설치하는데, 아래 사진에 나와있는 예외를 제외하고 한줄을 오갈 수 있으면 면 성공

---

풀이 방법

- 풀이 시간 : 2시간

- 접근 방식 : 브루트포스

 

일단 케이스는 4가지 였다.

1. 높이 차이가 2 이상인 경우: 경사로 설치 불가
2. 오르막길: 다음 값이 1 더 큼
3. 내리막길: 다음 값이 1 더 작음
4. 평평한 길: 현재 값과 다음 값이 같음

---

초기 접근(실패)

• Stack을 사용해서 같은 값이 들어올 때까지 쌓는 방식으로 접근
• 평평한 길, 오르막길, 높이차 2 이상인 경우는 비교적 처리 가능했음
• 하지만 내리막길의 경우,
  • 이미 설치된 경사로 위에는 또 경사로를 설치할 수 없다는 제약 때문에
  • Stack 방식으로는 로직이 지나치게 복잡해짐

예시

경사로 길이 L = 2
길: [2, 1, 1, 2, 1, 1]

 

• [2, 1, 1]은 내리막길이 잘 설치되어 통과 가능하지만,
• [1, 1, 2]는 오르막길 설치 시 앞의 경사로 위치와 겹치기 때문에 불가능

 

---

최종 해결 방법

 

• Stack을 버리고, 단순히 현재 위치와 다음 위치의 값을 비교하며 진행
• 오르막이거나 내리막일 경우, 경사로 길이만큼 앞 또는 뒤를 추가로 확인
• 확인 과정에서 다음 조건 체크:
  • 경계 벗어남
  • 경사로 설치 여부 (visited)
  • 높이 불일치
• 위 조건 중 하나라도 충족하지 않으면 불가능한 길로 처리

---

코드

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

public class Main {
    static int[][] map;
    static int N, L;
    static int count;
    static boolean[] visited;
    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());

        count = 0;
        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());
            }
        }

        for(int i = 0; i < N; i++){
            findLine(map[i]);
        }
        
        for(int j = 0; j < N; j++){
            int[] col = new int[N];
            for(int i = 0; i < N; i++){
                col[i] = map[i][j];
            }
            findLine(col);
        }

        System.out.println(count);
    }

    private static void findLine(int[] map){
        visited = new boolean[N];
        boolean flag = true;
        for(int i = 0; i < N-1; i++){
            int cur = map[i];
            int next = map[i+1];

            //1 커지는 경우(오르막)
            if(cur + 1 == next){
                for(int j = 0; j < L; j++){
                    int index = i-j;
                    if(index < 0 || visited[index] || map[index] != cur){
                        flag = false;
                        break;
                    }
                    visited[index] = true;
                }
            }else if (cur - 1 == next){         //1 작아지는 경우 내리막
                for(int j = 1; j <= L; j++){
                    int index = i+j;
                    if(index >= N || visited[index] || map[index] != next){
                        flag = false;
                        break;
                    }
                    visited[index] = true;
                }
                i += L - 1;
            }else if(Math.abs(cur - next) >= 2){  //2이상 차이나는 경우
                flag = false;
            }
        }
        if(flag){
            count++;
        }           
    }
}