구현 우웩

백준 14890번 구현문제를 풀어보았다. 로직 자체는 거의 근접했는데 마지막 센스가 좀 부족해서 결국 스스로 온전히 해결하지 못했다. 구현의 벽은 높다...!

문제가 하도 길어서 그냥 링크만 첨부하겠다.
https://www.acmicpc.net/problem/14890

---

문제가 겁나 복잡하다

감사하게도 이미지로 문제 부연 설명이 많아서 이해는 했다. 하지만 텍스트로 볼 때는 해결되지 않는 점이 하나 있었다. 가로에서 이미 경사로 설치를 해뒀다면 세로 관점에서 그 경사로는 무시해도 되는지에 대한 설명이 없었다.
하지만 그림에서 가능한 경로들을 이미지로 첨부한 것을 살펴보니 가로 세로는 서로 독립적으로 보면 되는 것임을 확인할 수 있었다.

더 작은 문제로 나눠 해결하자

나는 입력받은 이차원 배열 map을 그대로 썼다. 그래서 반복문이 좀 여러 개 겹쳐서 나오게 되어 더 복잡해서 코드를 치면 칠수록 더 머리가 아파졌다.

이를 해결하기 위해서 반복문 하나로 하나의 행, 하나의 열을 1차원 배열로 새롭게 입력받아 길 하나씩 해결해 나가면 된다.

하나의 길을 해결하기 위해 따로 가로지를 수 있는 길인지 확인하는 메소드를 선언했다.

static boolean isRoadable(int x, boolean rowOrCol){
        int[] height = new int[n];
        int[] extension = new int[n];
        for(int i=0; i<n; i++){
            if(rowOrCol)    height[i] = map[x][i]; // 행 검사
            else    height[i] = map[i][x]; // 열 검사
        }

        for(int i=0; i<n-1; i++){
            int displacement = height[i] - height[i+1];

            if(displacement==0) continue; // 똑같은 높이면 넘어가자
            else if(displacement==1){ // 좌측이 높고 우측이 낮을 때
                for(int j=i+1; j<=i+l; j++){
                    if(j>=n || height[i+1]!=height[j] || extension[j]==1)  return false;
                    extension[j] = 1;
                }
            }
            else if(displacement==-1){ // 좌측이 낮고 우측이 높을 때
                for(int j=i; j>i-l; j--){
                    if(j<0 || height[i]!=height[j] || extension[j]==1)  return false;
                    extension[j] = 1;
                }
            }
            else    return false;
        }

        return true;
    }

중간에 길을 만들 수 없는 조건을 만나게 되면 그냥 바로 return false를 때려버리면 된다. 위의 isRoadable메소드를 끝까지 가게 되면 길로 만들 수 있다는 거기 때문에 return true로 반환하면 된다.

아래는 내가 제출한 코드다.

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

public class boj14890 {
    static int n,l,road=0;
    static int[][] map,extension;

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        n = Integer.parseInt(stk.nextToken());
        l = Integer.parseInt(stk.nextToken());
        map = new int[n][n];
        extension = new int[n][n];
        for(int row=0; row<n; row++){
            stk = new StringTokenizer(bfr.readLine());
            for(int col=0; col<n; col++)
                map[row][col] = Integer.parseInt(stk.nextToken());
        }

        for(int i=0; i<n; i++){
            if(isRoadable(i, true)) road++; // 행 검사
            if(isRoadable(i, false)) road++; // 열 검사
        }

        bfw.write(String.valueOf(road));
        bfw.close();
    }

    static boolean isRoadable(int x, boolean rowOrCol){
        int[] height = new int[n];
        int[] extension = new int[n];
        for(int i=0; i<n; i++){
            if(rowOrCol)    height[i] = map[x][i]; // 행 검사
            else    height[i] = map[i][x]; // 열 검사
        }

        for(int i=0; i<n-1; i++){
            int displacement = height[i] - height[i+1];

            if(displacement==0) continue; // 똑같은 높이면 넘어가자
            else if(displacement==1){ // 좌측이 높고 우측이 낮을 때
                for(int j=i+1; j<=i+l; j++){
                    if(j>=n || height[i+1]!=height[j] || extension[j]==1)  return false;
                    extension[j] = 1;
                }
            }
            else if(displacement==-1){ // 좌측이 낮고 우측이 높을 때
                for(int j=i; j>i-l; j--){
                    if(j<0 || height[i]!=height[j] || extension[j]==1)  return false;
                    extension[j] = 1;
                }
            }
            else    return false;
        }

        return true;
    }
}

오늘 배운 것

1. 구현은 졸라 어렵다.
2. 코드가 복잡해지면 최대한 분리해보려 하자.