[백준/14890] 경사로(Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/14890
• 분류 : Simulation
• 풀이 시간 : 120분
  문제에 대한 조건을 하나씩 반영하고 예제 하나씩 돌려가면서 생각 못한 조건 또 반영하고..
  반복되는 코드 합쳐가면서 3번의 리펙토링을 거친 결과물..

문제 해설

1. 크기 NxN인 지도
2. 각 칸은 높이가 존재
3. 하나의 행 / 열 = 길
4. 길을 지나려면 '모든 칸의 높이가 동일' OR '지나갈 수 있도록 경사로 설치'
5. 경사로 조건
   1. 높이는 항상 1, 길이는 L
   2. 경사로는 낮은 칸과 높은 칸 연결 : 서로 높이의 차가 1이여야 함
   3. 경사로는 낮은 칸에 설치
   4. L개의 연속된 칸에 결사로의 바닥이 모두 접해햐 함
   5. 길의 범위 안에 경사로 설치해야 함
6. 지나갈 수 있는 길의 개수 구하시오

Solution

풀이 접근 방법

1. 경사로의 높이 = 1
   • 현재 칸과 다음 칸의 높이 비교 시 1 초과이면 경사로 설치 불가
   • 다른 칸 비교할 필요 없이 이동 자체가 불가능
2. 경사로의 길이만큼 바닥에 같은 수가 이어져야 한다 + 경사로는 상대적으로 낮은 칸에 놓임
   • 3(현재) > 2 (그 다음): 현재보다 하나 더 앞에 있는 칸부터 앞으로 탐색하면서 경사로 설치 여부 확인
     • 앞으로 탐색 = 만약 설치 가능하다면 그 다음 탐색할 칸 앞으로 당겨주기
   • 3(현재) > 4 (그 다음): 현재부터 뒤로 탐색하면서 경사로 설치 여부 확인
3. 길의 범위 안에 경사로 설치해야 함
   • 경사로 길이만큼 반복문 돌리면서 배열의 범위 넘어가지 않게 체크해줘야 함
4. 이미 놓은 부분에는 경사로 놓일 수 없음
   • EX) 경사로 길이 = 1, 칸의 높이 [3, 2, 1, 2, 3]일 때
   • 3 > 2 > 1 까지 경사로 놓고 1에서 2로 갈 때 경사로를 놓으면 갈 수 있지만,
   • 이미 이전에 2 > 1로 올 때 1에 경사로가 깔려있어서, 그 다음에 경사로 놓을 수 없음
   • => boolean[N] 배열로 해당 칸에 이미 설치한 경사로가 있는지 확인

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

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

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String[] info = br.readLine().split(" ");

    N = Integer.valueOf(info[0]);
    L = Integer.valueOf(info[1]);
    map = new int[N][N];
    roadCnt = 0;

    for (int i = 0; i < N; i++) {
      map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    solution();

    bw.write(roadCnt + "\n");
    bw.flush();
    bw.close();
  }

  static void solution() {
    for (int i = 0; i < N; i++) {
      // i 번째 행 지나갈 수 있는지 여부 확인
      if (roadSolution(map[i].clone())) {
        roadCnt += 1;
      }

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

      // i 번째 열 지나갈 수 있는지 확인
      if (roadSolution(colRoad)) {
        roadCnt += 1;
      }

    }
  }

  static boolean roadSolution(int[] road) {
    // 해당 칸에 경사로 설치 여부를 확인하는 배열
    boolean[] isInstall = new boolean[N];

    for (int i = 0; i < N - 1; i++) {
      // 다음 칸과의 높이 차가 1 초과 = 경사로를 놓아도 올라갈 수 없음
      // = 지나갈 수 없음
      if (Math.abs(road[i] - road[i + 1]) > 1)
        return false;

      // 같은 값이면 아무런 행동 없이 지나갈 수 있음
      if (road[i] == road[i + 1])
        continue;

      // 다음 칸이 한 칸 높으면
      // 올라가는 경사로 설치 : 1 -> 2
      if (road[i] + 1 == road[i + 1]) {
        // 경사로 = 낮은 칸에 설치해야 함
        // 현재 기준부터 뒤로 경사로 길이 만큼 반복문
        for (int j = i; j > i - L; j--) {
          // 범위 밖을 벗어나거나, 이미 해당 칸에 경사로 설치되어있거나, 값이 다르면 = 경사로 설치 불가
          // = 지나갈 수 없음
          if (j < 0 || isInstall[j] || road[i] != road[j])
            return false;
          isInstall[j] = true;
        }
      }
      
      // 다음 칸이 한 칸 낮으면
      // 내려가는 경사로 설치 : 2 -> 1
      if (road[i] - 1 == road[i + 1]) {
        // 현재 기준 앞으로 경사로 길이만큼 반복
        for (int j = i + 1; j <= i + L; j++) {
          if (j >= N || isInstall[j] || road[j] != road[i + 1])
            return false;
          isInstall[j] = true;
        }
        
        // 이미 i + L번 째 까지 경사로 설치
        // = i + L 까지는 같은 수 라는 의미
        // for문에서 마지막으로 i++해서 -1해주기
        i += L - 1;
      }
    }

    return true;
  }
}