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

 

 

문제 링크

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

문제 설명

리틀 프렌즈 사천성

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

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

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

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

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

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

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

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

입력 형식

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

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

출력 형식

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

예제 입출력

mnboardanswer

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이다.

 

---

풀이

풀이에 필요한 객체를 다음과 같이 정의하였다.

- Tile : 타일의 이름과 우선순위 정보를 가진 객체

- Point : 타일의 이름과 위치 정보를 가진 객체

 

Point는 이름이 같은 한 쌍의 타일들이 주어진 조건 안에서 이어지는지 여부를 확인하기 위해 사용된다.

Tile은 해당 타일이 지우는게 가능하다고 판단되고 우선순위큐에 저장되었을 때 순서를 지정하기 위해 사용된다.

 

문제 해결 순서는 다음과 같다.

1. 파라미터로 받은 board를 전연변수로 선언한 2차원 배열인 map에 값을 복사를 하면서 타입 이름별로 HashMap에 위치 정보(Point)를 저장한다.

2. HashMap에서 타일 이름별로 순회하면서 해당 타일이 현재 map 상태에서 지워지는지를 판별하여 지우도록 while문을 수행한다.

- 해당 순회는 더이상 순회할 타일이 없거나 이전 순회와 비교했을 때 지워진 타일이 없을 때까지 반복한다.

3. (while 내부) HashMap에서 타일명이 동일한 두 Point를 꺼내와서 지워지는 조건에 부합한지 확인 후, 부합하다면 removableTileList에 담는다.

4. (while 내부) 모든 key에 대한 순회가 끝나면 이번 차례에 지울 수 있는 타일 이름이 담긴 removableTileList를 오름차순으로 정렬하고, 가장 앞에 있는(알파벳이 가장 빠른) 타일을 우선순위큐에 추가하고 HashMap에서 제거한다.

5. 큐에 담긴 타일의 위치를 비어있도록(".") map에 반영한 뒤, priority++를 하고 while문을 반복

6. while문이 종료되고 HashMap에 여전히 남아있는 타일이 있는지 확인한다. 있다면 모든 타일을 지울 수 없는 케이스이므로 "IMPASSABLE"을 리턴

7. 큐에 담긴 타일을 차례대로 꺼내 이름을 answer에 반영하여 값 리턴

 

 

타일의 두 위치가 주어졌을 때 해당 타일이 지워지는 조건을 확인하는 로직이 중요했다고 생각한다.

"경로를 한 번 이하로 꺾을 수 있다."는 조건은 결국  dfs와 같이 모든 경로를 탐색하는 것이 아니라

두 타일의 지점을 꼭지점으로 하는 사각형을 그리고 그 사각형의 테두리 라인으로 가는 경로만 고려한다는 것을 의미한다.

 

이렇게 생각해볼 경우 타일의 위치가 크게 다음과 같이 두 가지로 나뉠 수 있다.

position1의 경우는 1+4의 경로 혹은 2+3의 경로로 연결했을 때 장애물 및 다른 이름의 타일이 없으면 제거 가능하다.

position2의 경우는 1+3의 경로 혹은 2+4의 경로로 연결했을 때 장애물 및 다름 이름의 타일이 없으면 제거 가능하다.

 

1과 2의 경로에서 유효성을 검증하는 기능을 checkWidth()에 작성하고, 3과 4의 경로에서 유효성을 검증하는 기능을 checkLength()에 작성하였다.

 

코드

import java.util.*;

public class Solution {

    private static final String IMPOSSIBLE_MESSAGE = "IMPOSSIBLE";
    private static final String EMPTY = ".";

    private String[][] map;

    public String solution(int m, int n, String[] board) {
        StringBuilder answer = new StringBuilder();
        Queue<Tile> queue = new PriorityQueue<>();
        Map<String, List<Point>> tiles = new HashMap<>();

        map = new String[m][n];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length(); j++) {
                map[i][j] = String.valueOf(board[i].charAt(j));

                if (Character.isUpperCase(board[i].charAt(j))) {
                    List<Point> pointList = tiles.getOrDefault(map[i][j], new ArrayList<>());
                    pointList.add(new Point(i, j, map[i][j]));
                    tiles.put(map[i][j], pointList);
                }
            }
        }

        int priority = 0;
        int beforeQueueSize = -1;

        while (!tiles.isEmpty() && beforeQueueSize != queue.size()) {
            beforeQueueSize = queue.size();
            List<String> removableTileList = new ArrayList<>();
            for (String key : tiles.keySet()) {
                List<Point> pointList = tiles.get(key);
                Point point1 = pointList.get(0);
                Point point2 = pointList.get(1);

                if (isRemovable(point1, point2)) {
                    removableTileList.add(point1.name);
                }
            }

            if (removableTileList.size() == 0) {
                continue;
            }

            Collections.sort(removableTileList);

            String name = removableTileList.get(0);
            List<Point> pointList = tiles.get(name);
            Point point1 = pointList.get(0);
            Point point2 = pointList.get(1);
            removeTile(point1.x, point1.y);
            removeTile(point2.x, point2.y);

            queue.add(new Tile(point1.name, priority));
            tiles.remove(name);

            priority++;
        }

        if (tiles.size() != 0) {
            return IMPOSSIBLE_MESSAGE;
        }

        while (!queue.isEmpty()) {
            Tile tile = queue.poll();
            answer.append(tile.name);
        }

        return answer.toString();
    }

    private void removeTile(int x, int y) {
        map[x][y] = EMPTY;
    }

    private boolean isRemovable(Point point1, Point point2) {
        String name = point1.name;

        int startX = Math.min(point1.x, point2.x);
        int endX = Math.max(point1.x, point2.x);
        int startY = Math.min(point1.y, point2.y);
        int endY = Math.max(point1.y, point2.y);

        int position = checkPosition(point1, point2);

        if (position == 1) {
            return (checkWidth(name, startX, endX, startY) && checkLength(name, startY, endY, endX)) || (checkWidth(name, startX, endX, endY) && checkLength(name, startY, endY, startX));
        }

        return (checkWidth(name, startX, endX, startY) && checkLength(name, startY, endY, startX)) || (checkWidth(name, startX, endX, endY) && checkLength(name, startY, endY, endX));
    }

    private boolean checkWidth(String name, int startX, int endX, int y) {
        for (int i = startX; i <= endX; i++) {
            if (map[i][y].equals(EMPTY) || map[i][y].equals(name)) {
                continue;
            }

            return false;
        }

        return true;
    }

    private boolean checkLength(String name, int startY, int endY, int x) {
        for (int j = startY; j <= endY; j++) {
            if (map[x][j].equals(EMPTY) || map[x][j].equals(name)) {
                continue;
            }

            return false;
        }

        return true;
    }

    private int checkPosition(Point point1, Point point2) {
        if (point1.x <= point2.x && point1.y <= point2.y) {
            return 1;
        }

        return 2;
    }

    class Tile implements Comparable<Tile> {
        String name;
        int priority;

        public Tile(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }

        @Override
        public int compareTo(Tile o) {
            if (this.priority == o.priority) {
                return this.name.compareTo(o.name);
            }

            return this.priority - o.priority;
        }
    }

    class Point {
        int x;
        int y;
        String name;

        public Point(int x, int y, String name) {
            this.x = x;
            this.y = y;
            this.name = name;
        }
    }
}