[프로그래머스] 87694 (아이템 줍기)

#1 오답 - 건강한(?) 실패

#1-1 코드

class Solution {
    int[][] visited = new int[51][51];

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[][] graph = getGraph(rectangle);

        // (BFS보다는) 코드를 좀 더 깔끔히 쓸 수 있는 DFS 선택
        dfs(graph, 1, characterY, characterX);

        return visited[itemY][itemX];
    }

    void dfs(int[][] graph, int length, int y, int x) {
        if (y < 1 || y > 50 || x < 1 || x > 50) {
            return;
        }

        if (graph[y][x] == 0 || graph[y][x] == -1) {
            return;
        }

        if (visited[y][x] == 0 || length < visited[y][x]) {
            visited[y][x] = length;
        } else {
            return;
        }

        String log = "(" + x + ", " + y + ")" + " " + length;
        System.out.println(log);

        dfs(graph, length + 1, y + 1, x);
        dfs(graph, length + 1, y - 1, x);
        dfs(graph, length + 1, y, x + 1);
        dfs(graph, length + 1, y, x - 1);
    }

    /*
    ~ 문제 속 문제 1 ~
    int[][] rectangle이 주어졌을때, 깔끔한 이동용 그래프를 만들어내어라.
    */
    int[][] getGraph(int[][] rectangles) {
    /*
    - 서로 다른 두 직사각형이 꼭짓점에서 만나는 경우는 없다
    - 서로 다른 두 직사각형의 각 변이 겹치는 경우는 없다
    - 어떤 직사각형 속에 또 다른 작은 직사각형이 쏙 들어가 있는 경우는 없다
    */
    
    /*
    위의 덕지덕지(?) 붙은 조건들로 미루어봤을때,
    저 조건들은 DFS/BFS 수행이 불가능한 경우를 (친절하게도) 쳐내주기 위한 조건으로 보인다.
    따라서, 어쩌면 복잡한 과정을 거쳐 '깔끔한' 이동용 그래프를 만들 필요없이 그냥 주는것을 그대로 받아적어도 되지 않을까? (가설)
    */
    
    /*
    0 = 아무것도 없음
    1 = 직사각형 테두리
    -1 = 직사각형 내부 <- 이 값으로, 직사각형 내부로 들어오는걸 방지할 수 있음
    */

        // index가 0인 자리는 미사용할 것임
        // 첫 차원은 y, 둘째 차원은 x
        int[][] graph = new int[51][51];
        for (int[] rectangle : rectangles) {
            updateGraph(graph, rectangle);
        }

        return graph;
    }

    // ~ 문제 속 문제 2 ~
    void updateGraph(int[][] graph, int[] rectangle) {
        int startY = rectangle[1];
        int endY = rectangle[3];
        int startX = rectangle[0];
        int endX = rectangle[2];

        for (int y = startY; y <= endY; y++) {
            for (int x = startX; x <= endX; x++) {
                if (y == startY || y == endY || x == startX || x == endX) {
                    if (graph[y][x] != -1) {
                        graph[y][x] = 1;
                    }
                } else {
                    graph[y][x] = -1;
                }
            }
        }
    }
}

 

#1-2 틀린 이유

// 로그 메시지
(1, 3) 1
(1, 4) 2
(2, 4) 3
(3, 4) 4
(3, 5) 5
(3, 6) 6 // (3, 5) → (3, 6)은 불가능한 이동
(4, 6) 7
...

테두리를 따라 움직이지 않고, 대륙 횡단을 해버렸다. 처음부터 문제를 꼼꼼히 읽고 시뮬레이션도 했더라면 발생하지 않았을 일인지도 모른다. 하지만, 이 오답은 다음 코드를 짜는 데 좋은 힌트가 된다. 즉 건강한(?) 실패라고 생각한다.

 

#2 오답 - 완벽주의의 늪

점을 하나의 클래스로 선언하고, 점 객체마다 독립적으로 이동 가능한 점을 명시하는 식으로 접근했다.

 

#2-1 코드

import java.util.ArrayList;

class Solution {
    static final int Y = 0;
    static final int X = 1;
    Point[][] points;

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        points = new Point[51][51];
        for (int y = 0; y < points.length; y++) {
            for (int x = 0; x < points[0].length; x++) {
                points[y][x] = new Point();
            }
        }
        updatePoints(rectangle);

        // (BFS보다는) 코드를 좀 더 깔끔히 쓸 수 있는 DFS 선택
        dfs(characterY, characterX, 0);

        return points[itemY][itemX].minAnswer;
    }

    void dfs(int y, int x, int answer) {
        Point point = points[y][x];

        if (point.isInner) {
            return;
        }

        if (!point.visited || answer < point.minAnswer) {
            point.visited = true;
            point.minAnswer = answer;
        } else {
            return;
        }

        String log = "(" + x + ", " + y + ")" + " " + point.minAnswer;
        System.out.println(log);

        for (int[] nextCoord : point.nextCoords) {
            dfs(nextCoord[Y], nextCoord[X], answer + 1);
        }
    }

    void updatePoints(int[][] rectangles) {
        for (int[] rectangle : rectangles) {
            int startY = rectangle[1];
            int endY = rectangle[3];
            int startX = rectangle[0];
            int endX = rectangle[2];

            for (int y = startY; y <= endY; y++) {
                for (int x = startX; x <= endX; x++) {
                    if (y == startY || y == endY || x == startX || x == endX) {
                        int[][] nextCoords = {
                                {y + 1, x},
                                {y - 1, x},
                                {y, x + 1},
                                {y, x - 1},
                        };

                        for (int[] nextCoord : nextCoords) {
                            if (nextCoord[Y] >= startY && nextCoord[Y] <= endY && nextCoord[X] >= startX && nextCoord[X] <= endX) {
                                points[y][x].nextCoords.add(nextCoord);
                            }
                        }
                    } else {
                        points[y][x].isInner = true;
                    }
                }
            }
        }
    }

    class Point {
        ArrayList<int[]> nextCoords = new ArrayList<>();
        boolean isInner = false;
        boolean visited = false;
        int minAnswer = 0;
    }
}

 

#2-2 틀린 이유

테스트 케이스

rectangle: [[2,2,5,5],[1,3,6,4],[3,1,4,6]]
characterX: 1
characterY: 4
itemX: 6
itemY: 3
result: 10

이 테스트 케이스를 통과하지 못했다.

 

그래프로 보기

정답은 검은색 자취인데, 내 코드는 빨간색 자취를 지나버린다. '이동 가능한 다음 좌표'를 결정하는 로직에 문제가 있는 것이다.

 

#2-3 방향 다잡기

#2는 부정확한 풀이였지만, 방향 자체가 '틀린 풀이'라고 할 수는 없었다. 하지만, 코딩 테스트는 주어진 시간 내에 문제를 해결하는 테스트고, 이 풀이는 결과적으로 부정확했을 뿐만 아니라 시간도 많이 소요되었다. 틀린 김에 아예 다른 방향을 몰색하는 게 맞다는 생각이 든다. 실은 #1에서 뇌리를 스친 아이디어가 있었는데, 그냥 흘려버리고 #2를 진행했었다. 바로, 문제 조건 자체를 2배로 확대하여 생각하는 것이다.

 

#3 정답

#3-1 코드

class Solution {
    final int MAP_LENGTH_SIZE = 50;
    final int DOUBLED_SIZE = MAP_LENGTH_SIZE * 2;
    int[][] visited = new int[DOUBLED_SIZE + 1][DOUBLED_SIZE + 1];

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[][] doubled_rectangles = new int[rectangle.length][4];
        int doubled_characterX = characterX * 2;
        int doubled_characterY = characterY * 2;
        int doubled_itemX = itemX * 2;
        int doubled_itemY = itemY * 2;

        for (int i = 0; i < doubled_rectangles.length; i++) {
            for (int j = 0; j < 4; j++) {
                doubled_rectangles[i][j] = rectangle[i][j] * 2;
            }
        }
        int[][] graph = getGraph(doubled_rectangles);

        // (BFS보다는) 코드를 좀 더 깔끔히 쓸 수 있는 DFS 선택
        dfs(graph, 1, doubled_characterY, doubled_characterX);

        return visited[doubled_itemY][doubled_itemX] / 2;
    }

    void dfs(int[][] graph, int length, int y, int x) {
        if (y < 1 || y > DOUBLED_SIZE || x < 1 || x > DOUBLED_SIZE) {
            return;
        }

        if (graph[y][x] == 0 || graph[y][x] == -1) {
            return;
        }

        if (visited[y][x] == 0 || length < visited[y][x]) {
            visited[y][x] = length;
        } else {
            return;
        }

        String log = "(" + x + ", " + y + ")" + " " + length;
        System.out.println(log);

        dfs(graph, length + 1, y + 1, x);
        dfs(graph, length + 1, y - 1, x);
        dfs(graph, length + 1, y, x + 1);
        dfs(graph, length + 1, y, x - 1);
    }

    // ~ 문제 속 문제 1 ~
    int[][] getGraph(int[][] rectangles) {
        int[][] graph = new int[DOUBLED_SIZE + 1][DOUBLED_SIZE + 1];
        for (int[] rectangle : rectangles) {
            updateGraph(graph, rectangle);
        }

        return graph;
    }

    // ~ 문제 속 문제 2 ~
    void updateGraph(int[][] graph, int[] rectangle) {
        int startY = rectangle[1];
        int endY = rectangle[3];
        int startX = rectangle[0];
        int endX = rectangle[2];

        for (int y = startY; y <= endY; y++) {
            for (int x = startX; x <= endX; x++) {
                if (y == startY || y == endY || x == startX || x == endX) {
                    if (graph[y][x] != -1) {
                        graph[y][x] = 1;
                    }
                } else {
                    graph[y][x] = -1;
                }
            }
        }
    }
}

2배로 입력하고, 최종 결과를 2로 나눈 것을 제외하면 #1의 코드와 완전히 동일한 논리의 코드다.

 

#3-2 교훈 & 앞으로의 전략

#3의 풀이 방식을 #1의 실패 직후 떠올렸음에도 묵살을 했던, 나의 심리는 뭐였을까? 단순하게 조건을 2배로 치환하여 푼다는 게 '그냥' 마음에 들지 않았던 것 같다. 그게 '편법'처럼 느껴졌다. 나는 '적절한 풀이'가 아닌, '완벽한 풀이'를 지향했다. 완벽주의의 영향일 것이다. 난이도도 결론도 불확실하지만, 더 완벽하고 '멋진' 풀이 방식을 선택하고 말았다.

 

사람이 단 번에 쨘하고 바뀔 수는 없다. 그러니 적어도, 완벽주의의 '득'과 '실'을 따지며 풀자. 완벽주의의 목소리를 따랐을 때 주어지는 득과 실이 무엇인지를 각각 명시적으로 밝혀보는 것이다. 이 문제에서는 완벽주의가 '실'로 발현되었지만, '득'일 때도 분명히 있긴 하다. 가령, '잘 읽히는 코드'를 지향하다보니 코드 가독성이 좋아져 긴 호흡의 구현을 할 때 도움이 되는 식이다.