Java - [프로그래머스]1836 - 리틀 프렌즈 사천성

출처

https://school.programmers.co.kr/learn/courses/30/lessons/1836#

프로그래머스

 

문제

 

요약하자면, 직선으로 연결 또는 1번 이하로 방향이 꺾인 선으로 연결하면 카드는 제거되며, 이 작업을 반복하였을때 모든 카드가 제거되는지, 제거된다면 제거된 카드의 순서를 구하는 문제이다.

직선은 다른 카드 위를 지나가거나 벽을 지나갈 수 없으며, 방향을 꺾을 시에는 단 1회만이 허용된다.

풀이

문제에서 제시한 조건을 그대로 구현하여 실행하는 시뮬레이션, 한마디로 그냥 구현 문제에 가깝다. 먼저 사전작업으로 아래와 같은 방식을 사용하였다.

• String[] 으로 주어지는 것을, 카드가 제거되고 나서 그 자리는 '.' 으로 업데이트 하는 작업을 해야했기에 char[][] 배열로 변환
• A - Z에 해당 되는 알파벳을 list에 넣어서 저장
• 카드는 각각 두장이기 때문에, Map 자료형을 사용하여 위치를 Node class로 변환하여 저장

처음에는 제거된 카드의 순서를 알기 위해 DFS를 사용하였고, 카드가 이어지는지 여부를 판단하기 위해 BFS를 사용하였다. DFS로 순열을 만들어 탐색을 진행했을때는 시간 초과가 발생하였고, BFS로 연결 여부를 판단하였을 때는 최단거리 순서에 따라 visited 여부가 미리 체크되어 있어 적합하지 않았다. 따라서 전부 갈아엎고 다시 처음부터 풀었다.

두번째로 풀었을 때는 BFS, DFS, 완전탐색 모두 사용하지 않고 아래와 같은 방식으로 해결할 수 있었다.

• 결과는 알파벳 순으로 빠른것을 하나만 구하면 된다.
• 그렇기 때문에 아까 카드 종류를 담아둔 list를 정렬하고, 리스트를 순회하며 해당 카드가 제거할 수 있는 카드인지 확인. 모든 카드가 제거가 될 때 까지 알파벳이 빠른 카드 부터 뒤에 있는 카드 까지 제거되는 것 차례로 카드를 제거해나가는 과정을 반복한다. (list.remove()를 사용)
• 만약 list 순회를 카드 종류의 갯수만큼 모두 반복했는데 원소가 남아있다면 모든 카드 제거에 실패한 것임으로 "IMPOSSIBLE" 출력

카드가 제거할 수 있는지 확인시 bfs를 사용하려면 visited 여부에 방향여부나 이런것들을 추가로 넣어서 체크해야 함으로 난이도가 훨씬 높다. 하지만, 조건에 방향전환을 1회 이하로 해야한다는 것이 있으므로 쉽게 해결할 수 있다.

왼쪽 그림을 보면 1번의 위치는 [0, 0], 2번의 위치는 [2, 2] 이다. 이 카드가 연결되기 위해서는 그림과 같이 직선 두개만 유효하면 된다.

• [1~2][0] (1번에서 2번의 좌표까지 아래로 내리는 직선) , [2][1~2] (내린 직선에서 출발하여, 2번의 y 방향으로 진행하는 직선)
• [0][1~2] (1번에서 2번의 y좌표까지 오른쪽으로 진행하는 직선), [1~2][2] (오른쪽으로 쭉 온 직선에서 출발하여 2번의 x까지 아래로 내리는 직선)

연결 하는 경우를 두가지 직선이라고 생각하고, 위 둘 중 하나의 경우만 만족해도 우리는 이것을 지울 수 있다고 판단할 수 있다. 따라서 bfs 없이도 간단하게 풀 수 있는 문제였다.

 

뭔가 요즘 반복적으로 그래프나 2차원 배열의 문제를 계속 풀다보니 의식적으로 그렇게 해야할 것 같아서 bfs나 dfs 부터 고려해서 문제를 해결했는데, 좀 더 깊이 생각하고 문제를 풀어야한다는 것을 깨닫게된 문제였다.

코드

import java.util.*;

class pgs1836 {
    char[][] board;
    int M, N, cardCnt;
    Map<Character, List<Node>> cardLocationInfoMap;
    List<Character> list;

    public String solution(int m, int n, String[] stringBoard) {
        String answer = "";
        board = new char[m][n];
        N = n;
        M = m;
        cardLocationInfoMap = new HashMap<>();
        cardCnt = 0;
        list = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = stringBoard[i].charAt(j);
                if (board[i][j] >= 'A' && board[i][j] <= 'Z') {
                    if (!cardLocationInfoMap.containsKey(board[i][j])) {
                        cardLocationInfoMap.put(board[i][j], new ArrayList<>());
                        list.add(board[i][j]);
                        cardCnt++;
                    }
                    cardLocationInfoMap.get(board[i][j]).add(new Node(i, j));
                }
            }
        }

        Collections.sort(list);
        int idx = 0;
        while(list.size() != 0){
            List<Node> nodes = cardLocationInfoMap.get(list.get(idx));
            if(canRemove(nodes.get(0), nodes.get(1), list.get(idx))) {
                char removed = list.remove(idx);
                answer += removed;
                board[nodes.get(0).x][nodes.get(0).y] = '.';
                board[nodes.get(1).x][nodes.get(1).y] = '.';
                idx = 0;
            }
            else{
                idx++;
                if(idx == list.size()){
                    return "IMPOSSIBLE";
                }
            }
        }

        return answer;
    }

    public boolean canRemove(Node node1, Node node2, char card) {
        if (node1.y < node2.y) {
            if (checkX(node1.x, node2.x, node2.y, card) && checkY(node1.y, node2.y, node1.x, card)) {
                return true;
            }
            if (checkX(node1.x, node2.x, node1.y, card) && checkY(node1.y, node2.y, node2.x, card)) {
                return true;
            }
        } else {
            if (checkX(node1.x, node2.x, node2.y, card) && checkY(node2.y, node1.y, node1.x, card)) {
                return true;
            }
            if (checkX(node1.x, node2.x, node1.y, card) && checkY(node2.y, node1.y, node2.x, card)) {
                return true;
            }
        }
        return false;
    }

    public boolean checkX(int x1, int x2, int y, char card) {
        for (int i = x1; i <= x2; i++) {
            if (board[i][y] != '.' && board[i][y] != card) {
                return false;
            }
        }
        return true;
    }

    public boolean checkY(int y1, int y2, int x, char card) {
        for (int i = y1; i <= y2; i++) {
            if (board[x][i] != '.' && board[x][i] != card) {
                return false;
            }
        }
        return true;
    }



    public boolean isRange(int x, int y) {
        return x >= 0 && x < M && y >= 0 && y < N;
    }

    public class Node{
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}