프로그래머스 / 리틀 프렌즈 사천성

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

자바

1. Sort를 해야하니 TreeMap을 이용하자. 
2. 길을 찾을 때 ㄱ 방향, ㄴ 방향을 고려해야 한다. 
3. 구현 문제다. 

import java.util.*;

class Solution {
    char[][] board;

    public String solution(int m, int n, String[] board) {
        this.board = new char[m][n];
        var pairs = new TreeMap<Character, List<int[]>>();
        for (var i = 0; i < m; i++)
            for (var j = 0; j < n; j++) {
                var temp = board[i].charAt(j);
                this.board[i][j] = temp;
                if (temp == '*' || temp == '.')
                    continue;
                if (!pairs.containsKey(temp))
                    pairs.put(temp, new ArrayList<>());
                pairs.get(temp).add(new int[]{i, j});
            }
        var answer = new StringBuilder();
        while (!pairs.isEmpty()) {
            char temp = '_';
            for (var k : pairs.keySet()) {
                var x1 = pairs.get(k).get(0)[0];
                var y1 = pairs.get(k).get(0)[1];
                var x2 = pairs.get(k).get(1)[0];
                var y2 = pairs.get(k).get(1)[1];
                if (check(y1, x1, x2, false, k) && check(x2, y1, y2, true, k)) {
                    delTile(x1, x2, y1, y2);
                    temp = k;
                    break;
                } else if (check(x1, y1, y2, true, k) && check(y2, x1, x2, false, k)) {
                    delTile(x1, x2, y1, y2);
                    temp = k;
                    break;
                }
            }
            if (temp == '_')
                return "IMPOSSIBLE";
            answer.append(temp);
            pairs.remove(temp);
        }
        return answer.toString();
    }

    boolean check(int stop, int from, int to, boolean yMove, char k) {
        if (from > to) {
            var temp = from;
            from = to;
            to = temp;
        }
        if (yMove) {
            for (var i = from; i <= to; i++)
                if (this.board[stop][i] != '.' && this.board[stop][i] != k)
                    return false;
        } else {
            for (var i = from; i <= to; i++)
                if (this.board[i][stop] != '.' && this.board[i][stop] != k)
                    return false;
        }
        return true;
    }

    void delTile(int x1, int x2, int y1, int y2) {
        this.board[x1][y1] = '.';
        this.board[x2][y2] = '.';
    }
}