[백준 Gold 3] 14890 경사로 - Java

문제링크 : https://www.acmicpc.net/problem/14890

14890번: 경사로

 

접근 과정 : 

• 문제에서 제시된 방법을 그대로 코드로 구현했다.
• 인접한 칸의 차이가 1이라면, 그에따라서 좌 혹은 우로 경사로를 설치할 수 있는지 확인했다.
• 가로길과 세로길로 탐색 방향만 다른 두개의 메소드를 만들어서 확인했다. 

 

소스 코드 및 결과 :

package BOJ;

/* 
    경사로
*/

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

public class BOJ14890 {

    public static void main(String[] args) throws IOException {

        init();

        int answer = countRoad();

        System.out.println(answer);

    }

    static int N, K;
    static int[][] map;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

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

    static boolean isPossibleForRow(int r) {

        boolean[] isUsed = new boolean[N];
        for (int i = 1; i < N; i++) {
            if (map[r][i] == map[r][i - 1]) {
                continue;
            }

            if (Math.abs(map[r][i] - map[r][i - 1]) > 1) {
                return false;
            }

            if (map[r][i - 1] - map[r][i] == 1) {

                if (N - i < K || isUsed[i]) {
                    return false;
                }

                isUsed[i] = true;
                for (int j = 1; j < K; j++) {
                    if (map[r][i] != map[r][i + j] || isUsed[i + j]) {
                        return false;
                    }
                    isUsed[i + j] = true;
                }

            } else if (map[r][i] - map[r][i - 1] == 1) {

                if (i < K || isUsed[i - 1]) {
                    return false;
                }

                isUsed[i - 1] = true;
                for (int j = 2; j <= K; j++) {
                    if (map[r][i - 1] != map[r][i - j] || isUsed[i - j]) {
                        return false;
                    }
                    isUsed[i - j] = true;
                }

            }
        }

        return true;
    }

    static boolean isPossibleForCol(int c) {

        boolean[] isUsed = new boolean[N];
        for (int i = 1; i < N; i++) {
            if (map[i][c] == map[i - 1][c]) {
                continue;
            }

            if (Math.abs(map[i][c] - map[i - 1][c]) > 1) {
                return false;
            }

            if (map[i - 1][c] - map[i][c] == 1) {

                if (N - i < K || isUsed[i]) {
                    return false;
                }

                isUsed[i] = true;
                for (int j = 1; j < K; j++) {
                    if (map[i][c] != map[i + j][c] || isUsed[i + j]) {
                        return false;
                    }
                    isUsed[i + j] = true;
                }

            } else if (map[i][c] - map[i - 1][c] == 1) {

                if (i < K || isUsed[i - 1]) {
                    return false;
                }

                isUsed[i - 1] = true;
                for (int j = 2; j <= K; j++) {
                    if (map[i - 1][c] != map[i - j][c] || isUsed[i - j]) {
                        return false;
                    }
                    isUsed[i - j] = true;
                }

            }
        }

        return true;
    }

    static int countRoad() {

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (isPossibleForRow(i)) {
                count++;
            }
            if (isPossibleForCol(i)) {
                count++;
            }
        }

        return count;
    }

}

 

P.S 

경사로 설치에 따라서, 불필요하게 중복방문하게 되는 곳이 있다.

그 부분을 제거한다면 더 효율적인 코드가 되지 않을까?