[백준-11112] Eight Puzzle (Astar Algorithm)

문제 요약

8-Puzzle 게임을 푸는 문제이다.

3x3 보드판에 한칸의 빈공간, 나머지 칸에는 1~8 숫자가 무작위로 위치해 있다.

빈칸과 숫자의 자리를 바꿔 이동시키며 정답을 찾아가는 게임이다.

입력으로 주어지는 보드는 1부터 8사이의 숫자가 섞여있으며 #은 빈 공간을 나타낸다.

빈공간과 인접한 칸의 숫자와 자리를 바꿔보며

원하는 보드의 모양을 만들기 위한 최소의 이동 횟수를 구하면 된다.

​

문제 풀이

기본적으로 탐색 알고리즘을 통해 풀 수 있는 문제이다.

이 문제에서 제한된 시간은 1초이며 테스트케이스는 100개이다.

제한된 시간 내에 효율적인 탐색 방법으로 풀어야 하는 문제이며

본문에서는 Astar Algorithm을 활용한 풀이를 기술한다.

 

Astar Algorithm은 미래에 가망 있는 값 (h 휴리스틱 값)을 구하면서

좀 더 답에 근접한 노드만 골라나가는 알고리즘이다.

 

출처 : https://ko.wikipedia.org/wiki/A*_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

가망성에 대한 가치 F값은 현재까지의 비용 (G) + 가망성 값(H)으로 정의한다.

즉, 정답과 현재 노드의 오차가 가장 작은 노드가 가장 정답에 빨리 도달할 수 있다고 보는 것이다.

​

기본적인 탐색 방법은 BFS와 동일하지만 모든 너비의 노드를 탐색하지 않고

가지치기를 통해 f값이 가장 작은 유망한 노드만 골라서 탐색해 나가는 방식이다.

큐에서 꺼낼 때 가망있는 노드가 우선성을 가진다는 점에서 본문의 풀이는 우선순위큐를 사용했다.

​

​

Solution

 

1. 최초의 보드를 우선순위 큐에 담고 3x3 보드의 형태를 한줄의 숫자열로 바꾸고 HashMap을 활용하여 재방문을 방지한다. HashMap의 key는 노드의 모양이고 value는 이동횟수가 된다.

​

* 우선순위 큐의 정렬 기준 두가지

​

* f값이 가장 작은 노드가 우선권을 가진다.

* f값이 동일한 노드끼리의 경우 g값(depth)이 더 작은 노드가 우선권을 가진다.

​

+

추가로 Time limit Error를 막기 위해 최적화 코드로 HashSet impossibleSet을 두었다.

테스트케이스를 수행하면서 불가능한 케이스를 만나면 불가능한 케이스를 만드는 과정들을 impossibleSet에 메모이제이션해놓았다.

이후 테스트케이스들에 대해 필터로 작용하며 불필요한 연산을 방지하였다.

 

 

    //이미 봤던 모양은 또 보지않기위해 key값으로 방문 여부 체크 
    static HashMap<Integer,Integer> visitMap = new HashMap<>();
    static HashSet<Integer> impossibleSet =  new HashSet<Integer>(); //memoization
    static PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2){
            //f = g+h라면 좀 더 이동횟수가 적었던 노드가 더 우선권을 가짐.
            if(o1.f==o2.f) return Integer.compare(o1.g,o2.g); 
            return Integer.compare(o1.f,o2.f); //f = g+h에서 f기준으로 정렬 
        }
    });
    static class Node{
        String board; //노드의 모양
        int g; //g(x)
        int f; //f(x)
        public Node(String data,int g,int f) {
            this.board = data;
            this.g=g;
            this.f=f;
        }
    }

 

 

2. while(우선순위 큐가 빌 때 까지)

2-1. 현재 빈공간과 자리를 바꿀 수 있는 숫자의 위치를 바꿔본다.

2-2. 바꾼 후 HashMap을 통해 이전에 방문한 모양은 보지않는다.

 

 

while(!pq.isEmpty()) {
            Node currentNode = pq.poll();
            String numberBoard = currentNode.board;
            int sharpIndex = numberBoard.indexOf("9"); //빈공간의 위치 인덱스
            int cr = sharpIndex/3;
            int cc = sharpIndex%3;
            
            //불가능한 케이스로 메모가 되어있는 경우 더이상 진행하지 않고 즉시 끝낸다.
            if(impossibleSet.contains(Integer.parseInt(numberBoard))) return;
            
            String data = "";
            for(int dir=0;dir<4;dir++){//move UP,RIGHT,LEFT,DOWN
                int nr = cr+dr[dir];
                int nc = cc+dc[dir];
                if(rangeCheck(nr,nc)){//영역을 만족 하는 경우
                    StringBuilder next = new StringBuilder(numberBoard);
                    next = swap(cr,cc,nr,nc,next); //swap
                    data = next.toString();
 
                    //이미 본 케이스면 건너뛴다.
                    if(visitMap.containsKey(Integer.parseInt(data))) continue; 
                    else {
                        /*
                         * heuristic logic
                         *f = g+h (현재 depth + 휴리스틱 값)
                         */
                        int g = currentNode.g;
                        int heuristic = getHeuristicValue(data); //h(x) 휴리스틱 function
                        int f = g+heuristic; 
                        pq.add(new Node(data,g+1,f));
                        visitMap.put(Integer.parseInt(data),g+1);
                    }
                }
            }
            //조사 후 
            if(visitMap.containsKey(Integer.parseInt("123456789"))) return; //찾았으면 끝냄 
            
        }

2-3. 현재 노드의 depth값과 휴리스틱 값을 더해 f값을 구한다.

휴리스틱 값은 Manhattan distance, 제자리에 위치하지 않은 숫자의 개수 등 여러 알고리즘으로 기준을 둘 수 있다. 이 때문에 Astar Algorithm의 퍼포먼스는 휴리스틱 function인 h(x)를 어떻게 짜느냐에 의존도가 높다.

본문에서는 제자리에 위치하지 않은 숫자의 개수로 가치를 두었다.

 

 

private static int getHeuristicValue(String data){
        //이미 목표 위치에 있는 숫자가 많을수록 더 가치있다고 판단하였다.   
        //Manhattan Distance나 다른 어떤 가치 판단 로직을 세워 
        //더 효율적인 휴리스틱 펑션을 만들어도 된다.
        int count = 0;
        for(int i=0;i<data.length();i++) {
            if("123456789".charAt(i)!=data.charAt(i)) count++;//같은 위치에 다른 숫자면 conut++
        }
        return count;
    }

 

3. 모든 과정이 끝나면 목표 노드와 일치하는 모양에 방문처리가 되어있는지를 확인하고 결과값을 출력한다.

이때 불가능한 결과에 대해서는 이후케이스의 불필요한 연산 시간을 줄이기 위해 memoization한다.

 

 

    for(int testcase=1;testcase<=T;testcase++) {
            br.readLine();//빈라인 read처리
            setData(); //Input
            astarAlgorithm(); //AstarAlgorithm
            if(visitMap.containsKey(Integer.parseInt("123456789"))) {
                bw.write((int) visitMap.get(Integer.parseInt("123456789"))+"\n");
                
            }else {//불가능하다는 판단이 나온 경우, 지나온 과정 모든 것이 불가능한 결과로 가는 과정이므로 Memoization 
                for(Integer key : visitMap.keySet()) impossibleSet.add(key);
                bw.write("impossible"+"\n");
            }
        }

 

Full code

 

 

public class EightPuzzle_Astar_Algorithm {
    static int T;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static char[][] board;
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};
    static HashMap<Integer,Integer> visitMap = new HashMap<>(); //이미 봤던 모양은 또 보지않기위해 key값으로 방문 여부 체크 
    static HashSet<Integer> impossibleSet =  new HashSet<Integer>(); //memoization
    static PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2){
            if(o1.f==o2.f) return Integer.compare(o1.g,o2.g); //f = g+h라면 좀 더 이동회수가 적었던 노드가 더 우선순위를 가짐.
            return Integer.compare(o1.f,o2.f); //f = g+h에서 f기준으로 정렬 
        }
    });
    static class Node{
        String board;
        int g; //g(x)
        int f; //f(x)
        public Node(String data,int g,int f) {
            this.board = data;
            this.g=g;
            this.f=f;
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        T = Integer.parseInt(br.readLine());
        for(int testcase=1;testcase<=T;testcase++) {
            br.readLine();//빈라인 read처리
            setData(); //Input
            astarAlgorithm(); //AstarAlgorithm
            if(visitMap.containsKey(Integer.parseInt("123456789"))) {
                bw.write((int) visitMap.get(Integer.parseInt("123456789"))+"\n");
                
            }else {//불가능하다는 판단이 나온 경우, 지나온 과정 모든 것이 불가능한 결과로 가는 과정이므로 Memoization 
                for(Integer key : visitMap.keySet()) impossibleSet.add(key);
                bw.write("impossible"+"\n");
            }
        }
        bw.flush();
        bw.close();
    }
    private static void astarAlgorithm(){
        while(!pq.isEmpty()) {
            Node currentNode = pq.poll();
            String numberBoard = currentNode.board;
            int sharpIndex = numberBoard.indexOf("9"); //빈공간의 위치 인덱스
            int cr = sharpIndex/3;
            int cc = sharpIndex%3;
            
            //불가능한 케이스로 메모가 되어있는 경우 더이상 진행하지 않고 즉시 끝낸다.
            if(impossibleSet.contains(Integer.parseInt(numberBoard))) return;
            
            String data = "";
            for(int dir=0;dir<4;dir++){//move UP,RIGHT,LEFT,DOWN
                int nr = cr+dr[dir];
                int nc = cc+dc[dir];
                if(rangeCheck(nr,nc)){//영역을 만족 하는 경우
                    StringBuilder next = new StringBuilder(numberBoard);
                    next = swap(cr,cc,nr,nc,next); //swap
                    data = next.toString();
                    
                    if(visitMap.containsKey(Integer.parseInt(data))) continue; //이미 본 케이스면 건너뛴다.
                    else {
                        /*
                         * heuristic logic
                         *f = g+h (현재 depth + 휴리스틱 값)
                         */
                        int g = currentNode.g;
                        int heuristic = getHeuristicValue(data); //h(x) 휴리스틱 function
                        int f = g+heuristic; 
                        pq.add(new Node(data,g+1,f));
                        visitMap.put(Integer.parseInt(data),g+1);
                    }
                }
            }
            //조사 후 
            if(visitMap.containsKey(Integer.parseInt("123456789"))) return; //찾았으면 끝냄 
            
        }
    }
    private static int getHeuristicValue(String data){
        //이미 목표 위치에 있는 숫자가 많을수록 더 가치있다고 판단하였다.   
        //Manhattan Distance나 다른 어떤 가치 판단 로직을 세워 더 효율적인 휴리스틱 펑션을 만들어도 된다.
        int count = 0;
        for(int i=0;i<data.length();i++) {
            if("123456789".charAt(i)!=data.charAt(i)) count++;//같은 위치에 같은 숫자면 conut++
        }
        return count;
    }
    private static StringBuilder swap(int cr, int cc, int nr, int nc, StringBuilder next) {
        int currentRC = cr*3+cc;
        int nextRC = nr*3+nc;
        char temp = next.charAt(currentRC);
        next.setCharAt(currentRC,next.charAt(nextRC));
        next.setCharAt(nextRC,temp);
        return next;
    }
    private static boolean rangeCheck(int nr, int nc){
        if(nr>=0 && nr<3 && nc>=0 && nc<3) return true;
        return false;
    }
    private static void setData() throws IOException {
        board = new char[3][3];
        visitMap.clear(); //새로운 케이스에 대한 초기화
        pq.clear();
        String boardStr="";
        for(int row=0;row<3;row++) {
            board[row] = br.readLine().toCharArray();
            for(int col=0;col<3;col++) {
                if(board[row][col]=='#') board[row][col] = '9'; //빈공간을 숫자 9로 치환한다. Integer.parseInt를 쓰기위함
                boardStr+=board[row][col];
            }
        }
        pq.add(new Node(boardStr,0,0));
        visitMap.put(Integer.parseInt(boardStr),0);
    }
}
 

github source 

https://github.com/Jangsukwoo/Algorithm/blob/master/Algo/src/CodingAcademy/EightPuzzle_Astar_Algorithm.java

Jangsukwoo/Algorithm

 

+

 

디버깅을 위한 추가 테스트 케이스는 이곳에서 확인할 수 있다.

https://github.com/marteloge/Programming-contests/tree/master/IDI%20Open/solutions/2008/idiopen2008data.dir

marteloge/Programming-contests

 

같은 문제

https://www.acmicpc.net/problem/1525

1525번: 퍼즐