[pro] 프로그래머스 level3 1836 리틀 프렌즈 사천성 (Java) - 시뮬레이션

[문제]

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

프로그래머스

 

[풀이]

모든 tile들을 사전순으로 list에 넣어놓고 반복문을 돌며 제거 가능한 타일은 제거(제거 후 '.'으로 바꿔서 넣어줌)하도록 한다. 제거 못한 타일이 있으면 IMPOSSIBLE을, 모든 타일에 대해 제거가 가능하다면 정답 문자열을 반환한다.

 

이 문제에서 고려해야 할 점은 타일을 제거하는 방법이다. 경로를 한 번 이하로 꺾을 수 있다고 문제 조건에 제시되어 있기 때문에 DFS 등을 이용해 모든 경로를 탐색할 필요가 없다. 두 타일을 꼭지점으로 하는 사각형을 생각했을 때, 사각형의 선분 경로로만 방해물 없이 이동하여 제거 가능한지를 확인하면 된다.

즉, 다음 2가지 경로에 대해서 확인해주면 된다.

 

출처: https://dev-note-97.tistory.com/255

 

[코드]

 

import java.util.*;

class Solution {
    char[][] map;
    List<Character> tiles = new ArrayList<>();
    Map<Character, List<Point>> hs = new HashMap<>();
    public String solution(int m, int n, String[] board) {
        String answer = "";
        map = new char[m][n];
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                map[i][j] = board[i].charAt(j);
            }
        }
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(map[i][j]>='A' && map[i][j]<='Z'){
                    if(!tiles.contains(map[i][j])){
                        tiles.add(map[i][j]);
                        //hs에 위치 저장
                        hs.put(map[i][j], new ArrayList<>());
                        hs.get(map[i][j]).add(new Point(i, j));
                    }else{
                        hs.get(map[i][j]).add(new Point(i, j));
                    }
                }
            }
        }
        
        Collections.sort(tiles);
        
        int idx = 0;
        while(tiles.size()!=0){
            char tile = tiles.get(idx);
            if(canRemove(tile)){
                char t = tiles.remove(idx);
                answer += t;
                //board에서 tile .으로 대체
                removeTile(t);
                idx = 0; //처음부터 다시 검사
            }
            else{
                idx++;
                if(idx==tiles.size()){
                    answer = "IMPOSSIBLE";
                    break;
                }
            }
        }
        
        return answer;
    }
    
    void removeTile(char t){
        Point p1 = hs.get(t).get(0);
        Point p2 = hs.get(t).get(1);
        
        map[p1.r][p1.c] = '.';
        map[p2.r][p2.c] = '.';
    }

    boolean canRemove(char tile){
        Point p1 = hs.get(tile).get(0);
        Point p2 = hs.get(tile).get(1);
        
        int r1 = p1.r;
        int c1 = p1.c;
        int r2 = p2.r;
        int c2 = p2.c;
        
        //왼쪽 상, 오른쪽 하 
        if(c1<c2){
            //ㄱ 모양 장애물 확인
            if(checkWidth(c1, c2, r1, tile) && checkHeight(r1, r2, c2, tile)){
                return true;
            }
            //ㄴ 모양 장애물 확인
            if(checkHeight(r1, r2, c1, tile) && checkWidth(c1, c2, r2, tile)){
                return true;
            }
        }
        //왼쪽 하, 오른쪽 상
        else{
            if(checkWidth(c2, c1, r1, tile) && checkHeight(r1, r2, c2, tile)){
                return true;
            }
            if(checkHeight(r1, r2, c1, tile) && checkWidth(c2, c1, r2, tile)){
                return true;
            }
            
        }
        return false;
    }
    
    boolean checkWidth(int c1, int c2, int r, char tile){
        for(int i=c1; i<=c2; i++){
            if(map[r][i]!='.' && map[r][i]!=tile){
                return false;
            }
        }
        return true;
    }
    
    boolean checkHeight(int r1, int r2, int c, char tile){
        for(int i=r1; i<=r2; i++){
            if(map[i][c]!='.' && map[i][c]!=tile){
                return false;
            }
        }
        return true;
    }
    
    static class Point{
        int r, c;
        Point(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}