[2017 카카오코드] 리틀 프렌즈 사천성 for JAVA

programmers.co.kr/learn/courses/30/lessons/1836

코딩테스트 연습 - 리틀 프렌즈 사천성

 

[문제 설명]

리틀 프렌즈 사천성

언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 준비해서 냄비에 넣고 휘젓기만 하면 순식간에 최고의 요리로 만들어주는 신비의 아이템. 어느 날 매직 스푼을 호시탐탐 노리는 악당들이 보물을 훔쳐간다. 매직 스푼을 되찾고 다시 마을에 평화를 가져오기 위해 프렌즈의 대모험이 시작되는데...

리틀 프렌즈 사천성은 프렌즈 사천성과 유사한 게임이다. 게임은 2차원 배열에서 진행되는데, 여러 가지 무늬로 구성된 타일이 배치되어 있으며 같은 모양의 타일은 두 개씩 배치되어 있다. 게임의 목적은 배치된 모든 타일을 제거하는 것으로, 같은 모양의 타일을 규칙에 따라 제거하면 된다. 타일을 제거할 수 있는 경우는 다음과 같다.

다음 조건을 만족하는 경로가 있을 때 두 타일을 제거할 수 있다.

• 경로의 양 끝은 제거하려는 두 타일이다.
• 경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다. (즉, 경로를 한 번 이하로 꺾을 수 있다)
  • 참고: 프렌즈 사천성은 경로가 세 개 이하의 선분으로 구성되어야 한다는 점이 다르다. (즉, 경로를 두 번 이하로 꺾을 수 있다)
• 경로 상에는 다른 타일 또는 장애물이 없어야 한다.

위의 배열에서 어피치 타일은 직선의 경로로 이을 수 있으므로 제거 가능하다. 라이언 타일 역시 한 번 꺾인 경로로 연결되므로 제거 가능하다. 무지 타일의 경우 다른 타일을 지나지 않는 경로는 두 번 꺾여야 하므로 제거할 수 없는 타일이며, 튜브 타일 역시 직선의 경로 사이에 장애물이 있으므로 제거 가능하지 않다.

타일 배열이 주어졌을 때, 규칙에 따라 타일을 모두 제거할 수 있는지, 그 경우 어떤 순서로 타일을 제거하면 되는지 구하는 프로그램을 작성해보자.

입력 형식

입력은 게임판의 크기를 나타내는 m과 n, 그리고 배치된 타일의 정보를 담은 문자열 배열 board로 주어진다. 이 배열의 크기는 m이며, 각각의 원소는 n글자의 문자열로 구성되어 있다. 입력되는 값의 제한조건은 다음과 같다.

• 1 <= m, n <= 100
• board의 원소는 아래 나열된 문자로 구성된 문자열이다. 각 문자의 의미는 다음과 같다.
  • .: 빈칸을 나타낸다.
  • *: 막힌 칸을 나타낸다.
  • 알파벳 대문자(A-Z): 타일을 나타낸다. 이 문제에서, 같은 글자로 이루어진 타일은 한 테스트 케이스에 항상 두 개씩만 존재한다.
  • board에는 알파벳 대문자가 항상 존재한다. 즉, 타일이 없는 입력은 주어지지 않는다.

출력 형식

해가 존재하는 경우 타일을 제거하는 순서대로 한 글자씩 이루어진 문자열을, 그렇지 않은 경우 IMPOSSIBLE을 리턴한다. 해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 리턴한다.

[풀이]

- 경로를 한 번 꺾어서 만날 수 있고, 경로는 수직, 수평으로 이루어져 있다. 또한 다른 타일이나 장애물이 없어야 한다.

- 한 테스트 케이스에서 알파벳은 항상 두 개 씩 존재한다.

- 알파벳 순이 빠른 경우의 답을 반환한다.

 

경로가 세 개가 아니고 두 개다. 여기서 얻을 수 있는 힌트는 알파벳 두 개가 가지고 있는 상, 하, 좌, 우의 이동 가능한 직선의 좌표만 알고 있으면 알파벳 두 개의 동선이 겹치는지 안 겹치는지 알 수 있다.

즉, 동선이 겹치면 해당 알파벳을 삭제할 수 있다.

 

문제 풀이 과정은

1. String[]로 주어진 board를 인덱스 처리와 비교를 쉽게 하기 위해 char[][] 의 식으로 2차원 배열로 바꿔준다.

2. 최소한의 반복문을 위해 문제에서 주어진 알파벳의 집합을 구한 뒤 정렬한다. 

(반복문 시작)

3. 정렬된 알파벳 배열에서 순서대로 알파벳 하나를 정한다.  

4. 해당 알파벳들이 위치한 좌표를 구한다.

5. 해당 알파벳들의 좌표가 겹치는지 확인한다.

6. 겹친다면 char[][] 배열에서 삭제한 뒤 값을 저장하고 알파벳 순서를 초기화한다. 삭제하지 못한다면 건너뛴다.

 

3 - 6 과정을 알파벳 배열이 끝날 때까지 한 번의 hit라도 되지 않는다면 반복문을 종료한다.

 

[코드]

public String solution(int m, int n, String[] board) {
        String answer = "";
        Set<Character> alSet = new HashSet<Character>(); // 알파벳 집합
        char[] dict = new char[alSet.size()];              // 알파벳 사전
        char[][] map = new char[m][n];                      // 2차원 배열 생성
        
        for (int i = 0; i < board.length; i++) {        //알파벳 집합 구하기
            for (int j = 0; j < n; j++) {
                if (board[i].charAt(j) == '.' || board[i].charAt(j) == '*') {
                    continue;
                } else {
                    alSet.add(board[i].charAt(j));
                }
            }
        }
 
        
        int setIdx = 0;
        Iterator<Character> iter = alSet.iterator();    //알파벳 사전
        while (iter.hasNext()) {
            dict[setIdx++] = iter.next();
        }
 
        Arrays.sort(dict);                                 //알파벳 순으로 정렬
 
        
        for (int i = 0; i < m; i++) {                    //2차원 배열 채우기
            for (int j = 0; j < n; j++) {
                map[i][j] = board[i].charAt(j);
            }
        }
 
        int rotate = 0; // 알파벳 집합 순환
        boolean check = false; // 알파벳이 끝까지 터지는 것이 없으면 종료
        while (true) {
            char alpabet = dict[rotate];
 
            if (alpabet != '!') {
                // 두 ArrayList에서 곂치는 부분 찾기
                ArrayList<String>[] meetPoint = getAvailableMove(map, alpabet);
                for (int i = 0; i < meetPoint[0].size(); i++) {
                    if (meetPoint[1].contains(meetPoint[0].get(i))) {
                        map = removeAlpabet(map, alpabet); // 알파벳 삭제
                        for (int j = 0; j < dict.length; j++) { // 사전에서도 삭제
                            if (dict[j] == alpabet) {
                                dict[j] = '!';
                            }
                        }
                        answer += alpabet;
                        check = true;
                        rotate = -1; // 처음으로 돌아가기 위한 로직
                        break;
                    }
                }
            }
 
            if (rotate == dict.length - 1) { // 종료 조건
                rotate = 0;
                if (!check) {                 //끝까지 돌았지만 check가 true를 만난적이 없어서(hit되지 않아서) 종료
                    break;
                }
                check = false;
            } else {
                rotate++;
            }
 
        }
 
        return answer.length() < alSet.size() ? "IMPOSSIBLE" : answer;
    }
 
    @SuppressWarnings("unchecked")
    public ArrayList<String>[] getAvailableMove(char[][] map, char alpabet) { // 두 알파벳의 움직일 수 있는 범위
        String[] alLocation = whereIsAlpabet(map, alpabet);
 
        String firstAl = alLocation[0]; // 알파벳 위치 찾기[ "i,j" , "i,j"]
        String secondAl = alLocation[1];
 
        ArrayList<String> firstAlpabet = setAvailableMove(map, Integer.parseInt(firstAl.split(",")[0]),
                Integer.parseInt(firstAl.split(",")[1]), alpabet);
 
        ArrayList<String> secondAlpabet = setAvailableMove(map, Integer.parseInt(secondAl.split(",")[0]),
                Integer.parseInt(secondAl.split(",")[1]), alpabet);
 
        ArrayList<String>[] alArr = new ArrayList[2];
        alArr[0] = firstAlpabet;
        alArr[1] = secondAlpabet;
 
        return alArr;
    }
    
    //알파벳이 움직일 수 있는 경로 구하기
    public ArrayList<String> setAvailableMove(char[][] map, int i, int j, char alpabet) {
        ArrayList<String> setMove = new ArrayList<String>();
        setMove.add(i + "," + j);
        // . 빈칸 *막힌 칸
        int go = 1;
        // 위
        while (i - go >= 0) {
            // System.out.println(go);
            if (map[i - go][j] == '.' || map[i - go][j] == alpabet) {
                setMove.add(Integer.toString(i - go) + "," + j);
                go++;
            } else {
                break;
            }
        }
 
        go = 1;
        // 아래
        while (map.length - 1 >= i + go) {
            if (map[i + go][j] == '.' || map[i + go][j] == alpabet) {
                setMove.add(Integer.toString(i + go) + "," + j);
                go++;
            } else {
                break;
            }
        }
        go = -1;
        // 왼쪽
        while (j + go >= 0) {
            if (map[i][j + go] == '.' || map[i][j + go] == alpabet) {
                setMove.add(i + "," + Integer.toString(j + go));
                go--;
            } else {
                break;
            }
        }
        go = 1;
        // 오른쪽
        while (j + go <= map[0].length - 1) {
            if (map[i][j + go] == '.' || map[i][j + go] == alpabet) {
                setMove.add(i + "," + Integer.toString(j + go));
                go++;
            } else {
                break;
            }
        }
 
        return setMove;
    }
 
    public String[] whereIsAlpabet(char[][] map, char alpabet) { // 알파벳 위치 찾기
        String[] location = new String[2];
        int idx = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (map[i][j] == alpabet) {
                    location[idx++] = i + "," + j;
                }
            }
            if (idx == 2)
                break;
        }
        return location;
    }
 
    public char[][] removeAlpabet(char[][] map, char alpabet) {    //2차원 배열에서 알파벳 삭제
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (map[i][j] == alpabet) {
                    map[i][j] = '.';
                }
            }
        }
        return map;
    }

테스트 케이스 통과

 

느낀 점 : 많이 어렵다. 해놓고 나면 쉬워만 보이는데 당장 코드를 짤 때는 쉽지 않다. 카카오 문제는 많은 조건들이 포함된다. 그 조건들이 또 다른 조건들에 영향을 준다. 더 열심히 해야 되는 것 밖에 없어 보인다.