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

문제 설명

이미지로 대체

레벨 3 문제.. 난 이틀동안 고민했다.. 😫

해결방법

해결방법은 처음에 DFS 나 BFS를 떠올렸다.
사실 어느 것으로 풀어도 문제는 없으나 DFS를 이용해서 문제를 해결하기로 결심.

DFS를 이용해서 꺽인 횟수를 체크해서 Map을 검색하여 같은 쌍을 찾으면 된다.

위와 같이 풀면 여러가지의 경우의 수가 나오는데, 가장 LexicalAlphabetically 한 답을 Return 하라였다.

소스코드

소스코드가 깔끔하지 못하다.
사실 첫 날에 거의 다 풀었는데, 둘 쨋날에 위문제를 보니 소스코드를 깔끔하게 고치기 싫었다..
그래서 중간중간 전역변수나 Set을 그대로 ArrayList에 박는등 그런 행위를 했다...(?)

import java.util.*;

class Solution {
    
    boolean isOk = false;
    int nextVisit = -1;
    boolean[] visited;
    public String solution(int m, int n, String[] board) {
        String answer = "";
        TreeSet<Character> set = new TreeSet<>();
        char[][] map = new char[m][n];
        
        for(int i=0; i<map.length; i++)
            map[i] = board[i].toCharArray();
        
        HashMap<Integer,ArrayList<Node>> results = new HashMap<>();
        
        for(int i=0; i<map.length; i++){
            for(int j=0; j<map[i].length; j++){
                if(Character.isAlphabetic(map[i][j]))
                    set.add(map[i][j]); 
            }
        }
        
        ArrayList<Character> check = new ArrayList<>(set);
        
        
        int index = 0;
        visited = new boolean[set.size()];
        while(true){
            ArrayList<Node> list = new ArrayList<>();
            isOk = false;
            
            
            for(int t=0; t<check.size(); t++){
                if(visited[t]) continue;
                char c = check.get(t);
                nextVisit = t;
                for(int i=0; i<m; i++){
                    for(int j=0; j<n; j++){
                        if(map[i][j]!=c) continue;
                        if(isOk) break;
                        findPair(list,map,i, j, i, j-1,0,0);
                        findPair(list,map,i, j, i-1, j , 1, 0);
                        findPair(list,map,i, j, i, j+1 , 2, 0);
                        findPair(list,map,i, j, i+1, j , 3, 0);
                    }
                    if(isOk) break;
                }
            }
            
            replace5ToPossible(map);
            
            if(list.isEmpty()) break;
            else {
                results.put(index++,list);
            }
        }
        
        String data = "";
        for(int key : results.keySet()){
            ArrayList<Node> list = results.get(key);
            Collections.sort(list);
            for(Node node : list){
                data+=node.word;
            }
        }
        
        for(boolean visit : visited)
            if(!visit) return "IMPOSSIBLE";
        
        return data;
    }
    
    public void replace5ToPossible(char[][] map){
        for(int i=0; i<map.length; i++){
            for(int j=0; j<map.length; j++){
                if(map[i][j]=='5') map[i][j] = '.';
            }
        }
    }
    
    public void findPair(ArrayList<Node> list,char[][] map,int firstX,int firstY, int endX,int endY,int direction, int level){
        if(endX<0||endY<0||endX>=map.length|| endY>=map[0].length) return;
        if(level>=2) return;
        if(map[firstX][firstY]>'Z'||map[firstX][firstY]<'A') return;
        if(firstX==endX&&firstY==endY) return;
        if(map[endX][endY]==map[firstX][firstY]&&map[endX][endY]<='Z'&&map[endX][endY]>='A'){
            int[] first = new int[2];
            first[0] = firstX;
            first[1] = firstY;
            int[] second = new int[2];
            second[0] = endX;
            second[1] = endY;
            list.add(new Node(first,second,map[endX][endY]));
            map[endX][endY] = '.';
            map[firstX][firstY] = '.';
            isOk = true;
            visited[nextVisit] = true;
            return;
        }else if(map[endX][endY]=='.'){
            int[] directionX = {0,-1,0,1};
            int[] directionY = {-1,0,1,0};
            for(int i=0; i<4; i++){
                if(direction!=i)
                    findPair(list,map,firstX,firstY,endX+directionX[i],endY+directionY[i],i,level+1);
                else
                    findPair(list,map,firstX,firstY,endX+directionX[i],endY+directionY[i],i,level);
            }
        }else
            return;
    }
}

class Node implements Comparable<Node>{
    public int[] first;
    public int[] second;
    public char word;
    
    public Node(int[] first, int[] second, char word){
        this.first = first;
        this.second = second;
        this.word = word;
    }
    
    @Override
    public int compareTo(Node other){
        return Character.compare(this.word, other.word);
    }
}

해결

그래도 해결했다는 점에서 뿌듯하긴 레벨 3문제던데 체감상 레벨 4 보다 어려웠다..

아니 생각자체는 빨리 떠올렸던 문젠데 많이 헤맸던 문제라 보는게 맞는 것 같다.