백준(BOJ) 1525 : 퍼즐 (JAVA)

문제링크 : https://www.acmicpc.net/problem/1525

1525번: 퍼즐

 

필자는 이 문제를 풀 때 '메모리 제한 32MB'라고 써있는 걸 보고, 메모리를 아끼기 위해 최선을 다하며 풀었다. 근데 지금 생각해보면 자바의 경우 256MB로 그렇게 적은 편이 아닌데 굳이 그렇게까지 했어야했나 싶기도 하다^^; 메모리를 아끼기 위해 혼신(?)의 힘을 쏟으며 푼 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    private static int[] di = {-1, 1, 0, 0};
    private static int[] dj = {0, 0, -1, 1};
    private static final int PUZZLE_SIZE = 3;
    private static final int FLATTED_SIZE = PUZZLE_SIZE * PUZZLE_SIZE;
    private static boolean[][] canSwap = new boolean[FLATTED_SIZE][FLATTED_SIZE];
    
    static {
        for(int i = 0; i < PUZZLE_SIZE; i++) {
            for(int j = 0; j < PUZZLE_SIZE; j++) {
                for(int k = 0; k < 4; k++) {
                    int nextI = i + di[k];
                    int nextJ = j + dj[k];
                    
                    if(nextI >= 0 && nextJ >= 0 && nextI < PUZZLE_SIZE && nextJ < PUZZLE_SIZE) {
                        canSwap[i * PUZZLE_SIZE + j][nextI * PUZZLE_SIZE + nextJ] = true;
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int initPuzzle = 0;
        int initZeroIdx = 0;
        
        for(int i = 0; i < PUZZLE_SIZE; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 0; j < PUZZLE_SIZE; j++) {
                int n = Integer.parseInt(st.nextToken());
                initPuzzle = initPuzzle * 10 + n;
                
                if(n == 0) {
                    initZeroIdx = i * PUZZLE_SIZE + j;
                }
            }
        }
        
        int min = bfs(initPuzzle, initZeroIdx);
        
        System.out.println(min);
    }
 
    private static int bfs(int initPuzzle, int initZeroIdx) {
        Queue<Status> queue = new LinkedList<Status>();
        Set<Integer> visited = new HashSet<Integer>();
        
        queue.offer(new Status(initPuzzle, 0, initZeroIdx));
        visited.add(initPuzzle);
        
        while(!queue.isEmpty()) {
            Status poll = queue.poll();
            int puzzle = poll.getPuzzle();
            int times = poll.getTimes();
            int zeroIdx = poll.getZeroIdx();
            
            if(puzzle == 123456780) {
                return times;
            }
 
            for(int i = 0; i < FLATTED_SIZE; i++) {
                if(canSwap[zeroIdx][i]) {
                    int next = swapNo(puzzle, zeroIdx, i);
                    
                    if(!visited.contains(next)) {
                        queue.offer(new Status(next, times + 1, i));
                        visited.add(next);
                    }
                }
            }
        }
        
        return -1;
    }
    
    private static int swapNo(int puzzle, int zeroIdx, int nextIdx) {
        int x = extractNo(puzzle, nextIdx);
        
        puzzle -= x * power(10, FLATTED_SIZE - 1 - nextIdx);
        puzzle += x * power(10, FLATTED_SIZE - 1 - zeroIdx);
        
        return puzzle;
    }
 
    private static int extractNo(int puzzle, int idx) {
        return (puzzle / power(10, FLATTED_SIZE - 1 - idx)) % 10;    
    }
    
    private static int power(int a, int n) {
        int ret = 1;
        
        for(int i = 0; i < n; i++) {
            ret *= a;
        }
        
        return ret;
    }
    
    private static class Status {
        private int puzzle;
        private int times;
        private int zeroIdx;
        
        public Status(int puzzle, int times, int zeroIdx) {
            this.puzzle = puzzle;
            this.times = times;
            this.zeroIdx = zeroIdx;
        }
 
        public int getPuzzle() {
            return puzzle;
        }
 
        public int getTimes() {
            return times;
        }
 
        public int getZeroIdx() {
            return zeroIdx;
        }
    }
}

전형적인 BFS문제이다. 메모리를 절약하기 위해 퍼즐의 상태를 2차원배열이 아닌, 정수로 변환해서 저장하는 것을 볼 수 있다. 또한 일반적으로 BFS를 풀 때는 방문여부(visited)를 boolean배열로 저장하지만, 이 경우에 boolean배열을 이용하려면 최소 876543211 크기의 배열을 선언해야하는데 대략 800MB정도 된다. 반면 Set으로 각각의 정수 값을 넣을 경우, 퍼즐에 배치될 수 있는 수의 모든 경우의 수가 9! = 362,880‬이기 때문에 훨씬 메모리를 절약할 수 있다. 그 밖에도 빈칸의 위치를 바꿀 때, char 배열로 잠깐 바꾼다음 swap하고 다시 정수로 바꾸면 편할텐데 메모리를 아끼기위해 계산을 통해 뽑아내는 눈물나는(?) 노력을 볼 수 있다ㅋㅋㅋ