[프로그래머스] 리틀 프렌즈 사천성 - 실패 코드

- bfs로 풀어보려고 했으나 테케는 다 통과하는데 답은 빠르게 no를 뱉는다.

- 예외 상황 커버가 더 필요한 듯 보입니다.

- 본질적으로는 구현 문제 같아서 완성된 코드 참고만 하고 넘어감.

 

 

import java.util.*;
class Point {
    int x;
    int y;
    char c;
    int d; // 0: 시작 1: 하 2: 좌 3: 우
    int curveCount;
    public Point(int x, int y, char c, int d, int curveCount) {
        this.x = x;
        this.y = y;
        this.c = c;
        this.d = d;
        this.curveCount = curveCount;
    }

    public char getC() {
        return c;
    }

    public void increaseCurveCount() {
        this.curveCount++;
    }

}
class Solution {
    public String solution(int m, int n, String[] board) {
        String answer = "";
        char[][] map = new char[m][n];
        for(int i=0; i<m; i++) {
            map[i] = board[i].toCharArray();
        }

        List<Point> needChars = new ArrayList();
        List<Point> removeChars = new ArrayList();
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                char currentC = map[i][j];
                boolean containsC = needChars.stream().anyMatch(o -> o.getC() == currentC);
                if(currentC != '*' && currentC != '.' && !containsC ) {
                    needChars.add(new Point(i, j, currentC, 0, 0));
                }
            }
        }

        int charSize = needChars.size();
        List<Character> answerArr = new ArrayList();

        needChars.sort((a, b) -> a.c - b.c);

        boolean canGoNextStep = true;
        while(canGoNextStep) {
            canGoNextStep = false;
            for(int i=0; i<needChars.size(); i++) {
                // System.out.println(needChars.get(i).c);
                // System.out.println(availableCharRight(needChars.get(i), map));
                // System.out.println(availableCharLeft(needChars.get(i), map));
                boolean isAvailable = availableCharRight(needChars.get(i), map) || availableCharLeft(needChars.get(i), map);
                if(isAvailable) {
                    canGoNextStep = true;
                    // for(int j=0; j<m; j++) {
                    //     for(int k=0; k<n; k++) {
                    //         System.out.print(map[j][k] + " ");
                    //     }
                    //     System.out.println("");
                    // }
                    removeChars.add(needChars.get(i));
                    break;
                }
            }

            for(int i=0; i<removeChars.size(); i++) {
                needChars.remove(removeChars.get(i));
                removeMatch(removeChars.get(i).c, map);
                answerArr.add(removeChars.get(i).c);
            }
            removeChars = new ArrayList();
        }

        for(int i=0; i<answerArr.size(); i++) {
            System.out.println(answerArr.get(i));
        }

        if(answerArr.size() != charSize ) {
            return "IMPOSSIBLE";
        }

        answer = answerArr.stream().map(e->e.toString()).reduce((acc, e) -> acc  + e).get();

        return answer;
    }

    private boolean availableCharRight(Point p, char[][] map) {
        Queue<Point> q = new LinkedList();
        q.add(p);
        while(!q.isEmpty()) {
            // 우, 하로 이동
            Point cp = q.poll();
            int cx = cp.x;
            int cy = cp.y;
            int[] dx = new int[]{1, 0};
            int[] dy = new int[]{0, 1};
            for(int i=0; i<2; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                // i == 0 하, i == 1 우
                if(inSideMap(nx, ny, map.length, map[0].length, p.x, p.y)) {
                    Point np = new Point(nx, ny, map[nx][ny], i+1, cp.curveCount);
                    if(cp.d != np.d) {
                        np.increaseCurveCount();
                    }
                    if(map[nx][ny] == '.') {
                        q.add(np);
                    }
                    if(np.curveCount < 3 && p.c == map[nx][ny]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean availableCharLeft(Point p, char[][] map) {
        Queue<Point> q = new LinkedList();
        q.add(p);
        while(!q.isEmpty()) {
            // 좌, 하로 이동
            Point cp = q.poll();
            int cx = cp.x;
            int cy = cp.y;
            int[] dx = new int[]{1, 0};
            int[] dy = new int[]{0, -1};
            for(int i=0; i<2; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                // i == 0 하, i == 1 좌
                if(inSideMap(nx, ny, map.length, map[0].length, p.x, p.y)) {
                    Point np = new Point(nx, ny, map[nx][ny], i+1, p.curveCount);
                    if(cp.d != np.d) {
                        np.increaseCurveCount();
                    }
                    if(map[nx][ny] == '.') {
                        q.add(np);
                    }
                    if(np.curveCount < 3 && p.c == map[nx][ny]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean inSideMap(int x, int y, int m, int n, int cx, int cy) {
        return x >= 0 && x < m && y >= 0 && y < n && !(cx == x && cy == y);
    }

    private void removeMatch(char c, char[][] map) {
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                if(c == map[i][j]) {
                    map[i][j] = '.';
                }
            }
        }
    }
}