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

문제 보기

사용한 것

• 경사로의 도움을 받는 지, 경사로의 도움 없이 얼만큼 이동했는지를 나타내는 int support

풀이 방법

support는 내리막 경사로를 사용할 때 경사로 크기에 따라 커진다.
support는 오르막 경사로를 사용할 때 음수 크기가 경사로의 크기만큼 충분해야 한다.
support는 한칸씩 건널 때마다 1 감소한다.

• 풀이의 구성은 다음과 같다.
• 입력 받은 n 만큼의 for 문
• 그 안에 행을 나타내는 for 문, 열을 나타내는 for 문 한번 씩
• 로직은 다음과 같다.
• 경사로의 도움을 받고 있을 때
  • 현재 경사로를 쓰고 있음에도 높이가 다르면 건널 수 없다.
• 경사로의 도움을 받고 있지 않을 때
  • 현재 높이가 h보다 1 작은 경우에는 범위 안에 경사로를 놓을 수 있으면 일단 경사로를 놓는다. h를 1 감소시키고 support를 l - 1로 설정한다.
  • 현재 높이가 h보다 1 큰 경우에는 현재까지 경사로 없이 건너온 수가 support에 음수로 기록되므로, 해당 크기가 l보다 크거나 같으면 건널 수 있다.
  • 두 경우를 제외하고 cur과 h가 다르면 건널 수 없다.
  • cur과 h가 같은 경우 support를 1 감소한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int l = Integer.parseInt(line[1]);
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            map[i] = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            int h = map[i][0];
            boolean check = true;
            int support = 0;
            for (int j = 0; j < n; j++) {
                int cur = map[i][j];

                if (support > 0) { // 아직 경사로가 남았을 때
                    if (cur != h) {
                        check = false;
                        break;
                    }
                    support--;
                } else { // 경사로 없을 때
                    if (cur == h - 1) {
                        if (j + l > n) {
                            check = false;
                            break;
                        }
                        h--;
                        support = l - 1;
                    } else if (cur == h + 1) {
                        if (-support < l) {
                            check = false;
                            break;
                        }
                        h++;
                        support = -1;
                    } else if (cur != h) {
                        check = false;
                        break;
                    } else {
                        support--;
                    }
                }
            }

            if (check) {
                answer++;
            }

            h = map[0][i];
            check = true;
            support = 0;
            for (int j = 0; j < n; j++) {
                int cur = map[j][i];

                if (support > 0) { // 아직 경사로가 남았을 때
                    if (cur != h) {
                        check = false;
                        break;
                    }
                    support--;
                } else { // 경사로 없을 때
                    if (cur == h - 1) {
                        if (j + l > n) {
                            check = false;
                            break;
                        }
                        h--;
                        support = l - 1;
                    } else if (cur == h + 1) {
                        if (-support < l) {
                            check = false;
                            break;
                        }
                        h++;
                        support = -1;
                    } else if (cur != h) {
                        check = false;
                        break;
                    } else {
                        support--;
                    }
                }
            }

            if (check) {
                answer++;
            }
        }

        System.out.println(answer);
    }
}