[프로그래머스 Level.3] 리틀 프렌즈 사천성 (2017 카카오코드 본선) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 2017 카카오코드 본선 > 리틀 프렌즈 사천성

 

 

 

문제 설명

 

 

리틀 프렌즈 사천성

 

언제나 맛있는 음식들이 가득한 평화로운 푸드 타운.
푸드 타운에서 행복하게 사는 리틀 프렌즈들은
마을에 있는 매직 스푼을 보물처럼 보관하고 있다.

매직 스푼은 재료만 준비해서 냄비에 넣고 휘젓기만 하면
순식간에 최고의 요리로 만들어주는 신비의 아이템.
어느 날 매직 스푼을 호시탐탐 노리는 악당들이 보물을 훔쳐간다.

매직 스푼을 되찾고 다시 마을에 평화를 가져오기 위해
프렌즈의 대모험이 시작되는데...

 

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

 

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

 

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

 

 

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

 

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

 

 

 

입력 형식

 

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

 

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

 

 

 

출력 형식

 

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

 

 

 

 

예제 입출력

m	n	board	answer
3	3	["DBA", "C*A", "CDB"]	"ABCD"
2	4	["NRYN", "ARYA"]	"RYAN"
4	4	[".ZI.", "M.**", "MZU.", ".IU."]	"MUZI"
2	2	["AB", "BA"]	"IMPOSSIBLE"

 

 

 

예제에 대한 설명

 

첫 번째 테스트 케이스에서 처음으로 제거 가능한 타일은 A와 C이다. 그리고 모든 가능한 경우를 나열하면 ABCD, ACBD, ACDB, CABD, CADB, CDAB이다. 이 중 알파벳 순으로 가장 먼저인 ABCD가 정답이다.

네 번째 테스트 케이스는 초기 상태에서 제거할 수 있는 타일이 없으므로 타일을 모두 제거하는 것이 불가능하다. 따라서 정답은 IMPOSSIBLE이다.

 

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    char[][] boards;
    ArrayList<Character> list;
    HashMap<Character, ArrayList<Point>> map;
    public String solution(int m, int n, String[] board) {
        String answer = "";
        boards = new char[m][n];
        list = new ArrayList<>();
        map = new HashMap<>();
       
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                char c = board[i].charAt(j);
                boards[i][j] = c;
                
                if(c != '.' && c != '*') {
                    if(!list.contains(c)) {
                        list.add(c);
                        map.put(c, new ArrayList<>());
                    }
                    map.get(c).add(new Point(i, j));
                }
            }
        }
        
        Collections.sort(list); // 해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 리턴하기 때문에 오름차순 정렬을 하고 진행한다.
        
        int idx = 0;
        while(!list.isEmpty()) {
            if(canDelete(list.get(idx))) {
                char c = list.remove(idx);
                answer += String.valueOf(c);
                ArrayList<Point> pointList = map.get(c);
                boards[pointList.get(0).row][pointList.get(0).col] = '.';
                boards[pointList.get(1).row][pointList.get(1).col] = '.';
                idx = 0;
            } else {
                idx++;
                if(idx == list.size()) return "IMPOSSIBLE";
            }
        }
        
        return answer;
    }
    
    private boolean canDelete(char c) {
        ArrayList<Point> pointList = map.get(c);
        int row1 = pointList.get(0).row;
        int col1 = pointList.get(0).col;
        int row2 = pointList.get(1).row;
        int col2 = pointList.get(1).col;
        
        // 좌표는 결국 직사각형의 두 꼭짓점이기 때문에 두개의 경로를 체크하면 된다.
        if(col1 < col2) { // [row1][col1]이 왼쪽 위에 있고 [row2][col2]가 오른쪽 아래 or 같은 행에서 [row1][col1]이 왼쪽에 있고 [row2][col2]가 오른쪽
            // ㄱ자로 확인
            if(linearColumnCheck(col1, col2, row1, c) && linearRowCheck(row1, row2, col2, c)) return true; 
            // ㄴ자로 확인
            if(linearRowCheck(row1, row2, col1, c) && linearColumnCheck(col1, col2, row2, c)) return true;
                
        } else { // [row1][col1]이 오른쪽 위에 있고 [row2][col2]가 왼쪽 아래 or 같은 열에서 [row1][col1]이 위쪽에 있고 [row2][col2]가 아래쪽
            // ┎자로 확인
            if(linearRowCheck(row1, row2, col2, c) && linearColumnCheck(col2, col1, row1, c)) return true;
            // ┘자로 확인
            if(linearColumnCheck(col2, col1, row2, c) && linearRowCheck(row1, row2, col1, c)) return true;
        }
        
        return false;
    }
    
    private boolean linearRowCheck(int row1, int row2, int col, char c){
        for(int i=row1; i<=row2; i++) {
            if(boards[i][col] != '.' && boards[i][col] != c) return false;
        }
        
        return true;
    }
    
    private boolean linearColumnCheck(int col1, int col2, int row, char c){
        for(int i=col1; i<=col2; i++) {
            if(boards[row][i] != '.' && boards[row][i] != c) return false;
        }
        
        return true;
    }
    
    class Point {
        int row;
        int col;
        
        private Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

 

풀이

1. char형 2차원 배열 boards을 만들어 board를 각 문자로 변환하여 2차원 배열 boards에 담는다.
2. '.'과 '*'가 아닌 타일의 문자 종류를 담기 위해 ArrayList를 생성한다.
3. 좌표의 행(row)과 열(col)을 멤버 변수로 갖는 Point 클래스를 생성한다.
4. 문자의 종류 별로 각 2개씩의 타일의 위치를 담기 위해 key를 Character로 하고 value를 Point를 선언타입으로 갖는 ArrayList로 하는 Map을 생성한다.
5. 이제 boards를 전체 좌표를 이중 for문을 돌면서 해당 문자가 '.'과 '*'가 아니고 ArrayList에 담겨있지 않으면 ArrayList에 담고 Map에 해당 문자를 key로 하고 value에 해당 좌표를 이용해 Point를 만들어 담는다. (Point는 같은 행에 있으면 두 Point의 row가 같고 아니면 더 위에 있는(row가 작은) 타일의 좌표가 먼저 담긴다)
6. 해가 여러 가지인 경우 알파벳 순으로 가장 먼저인 문자열을 리턴하라고 하였으니 ArrayList를 사전순으로 정렬한다.
7. 모든 문자를 제거하기 위해서 ArrayList가 빌 때까지 while문을을 돌면서 해당 문자를 제거 할 수 있으면 제거하고 그 자리를 '.'(빈칸)으로 채운 후에 해당 문자를 answer에 추가한다. 문자를 제거 할 수 없으면 다음 문자를 확인하도록 하며 만약 마지막 문자까지 가도 제거하지 못한다면 "IMPOSSIBLE"을 리턴한다.
8. ArrayList를 돌면서 인덱스를 관리하기 위해 idx를 0으로 초기화하고 while문을 진행한다.
9. idx에 해당하는 ArrayList의 인덱스의 문자를 제거할 수 있는지 확인하고 제거할 수 있다면 ArrayList에서 해당 인덱스를 제거하고 answer에 해당 문자를 추가하고 Map에서 해당 문자의 좌표 2개를 가져와 해당 좌표를 '.'(빈칸)으로 변경하고 idx를 0으로 변경하여 다시 ArrayList의 처음부터(사전순 앞부터) 다시 확인한다.
10. 문자를 제거 할 수 없다면 idx를 증가시키고 다시 ArrayList의 해당 idx의 인덱스에 해당 문자로 확인하며 ArrayList의 끝까지 가도 제거 할 수 없다면  문자를 전부 제거할 수 없는 것이므로 "IMPOSSIBLE"을 반환하면 된다.
11. 문자를 제거할 수 있는지 확인하는 것은 해당 문자의 두 좌표를 Map에서 가져와 먼저 담은 Point의 row1이 다음에 담은 Point의 row2보다 같거나 작으므로 두 좌표의 열 좌표를 비교하면 어떤 경로로 확인을 해야할지 알 수 있다. (직사각형의 네 꼭짓점 좌표 중 2개이기 때문에 대각선에 있는 경우, 같은 열에 있는 경우, 같은 행에 있는 경우 이렇게 3가지 뿐이기 때문이다) 
12. 따라서 col1이 col2보다 작다면 [row1][col1]이 왼쪽 위에 있고 [row2][col2]가 오른쪽 아래에 있거나 같은 행에서 [row1][col1]이 왼쪽에 있고 [row2][col2]가 오른쪽에 있는 두 가지 경우이므로 ㄱ자 방식로 확인하거나 ㄴ자 방식으로 확인하면 된다.
13.  col1이 col2보다 같거나 크다면 [row1][col1]이 오른쪽 위에 있고 [row2][col2]가 왼쪽 아래에 있거나 같은 열에서 [row1][col1]이 위쪽에 있고 [row2][col2]가 아래쪽에 있는 두 가지 경우이므로 ┌ 방식으로 확인하거나 ┘방식으로 확인하면 된다.
14. 확인 하는 방법은 해당 두 좌표들을 이용하여 for문을 통해 해당 탐색 방식 직선상에 벽이 오거나 다른 문자가 오면 타일이 제거 불가능하다.
15. 모든 문자를 제거했다면 answer를 반환하면 된다.

 

참고 : https://dev-note-97.tistory.com/255