[백준] 1525 퍼즐

www.acmicpc.net/problem/1525

1525번: 퍼즐

2020-12-06

---

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main1525 {
    public static int answer;
    public static boolean flag;
    public static String base;
    public static HashSet<String> set;
    public static Queue<String> q;
    public static int dx[] = {-1, 1, -3 ,3};
    
    public static String swap(String sb, int cur, int next) {
        StringBuilder tmp = new StringBuilder(sb);
        char c = tmp.charAt(cur);
        char n = tmp.charAt(next);
        
        tmp.setCharAt(cur, n);
        tmp.setCharAt(next, c);
        
        return tmp.toString();
    }
    
    public static void solve() {
        loop:while(!q.isEmpty()) {
            int size = q.size(); 
            lop:while(size > 0) {
                String str = q.poll();
                int x = str.indexOf("0");
                if(str.equals("123456780")) {
                    flag = true;
                    break lop;
                }
                for(int i = 0;i < dx.length; i++) {
                    int nx = x + dx[i];
                    
                    if(nx < 0 || nx >= 9 || (i == 1 && (x+1)%3 == 0 ) || (i == 0 && x % 3 == 0)) continue;
                    else {
                        String next = swap(str, x, nx);
                        if(!set.contains(next)) {
                            set.add(next);
                            q.add(next);
                        }
                    }
                }
                size--;
            }
            if(flag) break loop;
            answer++;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        q = new LinkedList<>();
        flag = false;
        answer = 0;
        base = "";
        for(int i = 0 ; i <3; i++) {
            for(int j = 0; j < 3; j++) {
                int x= sc.nextInt();
                base += x;
            }
        }
        set = new HashSet<>();
        q.add(base);
        set.add(base);
        solve();
        if(flag) System.out.println(answer);
        else System.out.println("-1");
    }
}

브루트 포스(중복을 거르면서) + BFS로 풀었다.

 

#문제 풀이

1. 2차원 배열이 아닌 String 형태로 값을 받는다. 

 

2. HashSet에 중복제거를 위하여, 새로운 퍼즐의 값들을 넣어준다. 그 첫번째로, 처음 입력 받은 값도 넣어준다.

 

3. queue에 처음 입력받았던 string을 넣어주었다. 

 

4. String형태에서 각 글자에 index를 생각하고, 0이 움직일 수 있는 인덱스를 생각하면 { -1, 1, -3, 3 } 4가지 방향이 나온다. queue에 값을 꺼내서 답이 "123456780" 이 아닌 경우는 이 4가지 방향대로 swap하면서, 새로운 String을 만든다. 이 때 HashSet을 사용하여, 중복이 아닌 경우에만 새로운 queue에 넣는다.

 

# 포인트

1. 메모리 초과

- 메모리 제한이 있다. (32MB) 

- 처음에는 class를 생성해서, current 0의 위치와 그 때의 String값을 동시에 저장했는데, 메모리 초과가 떴었다. 생각해보니 current 위치를 string과 함께 굳이 같이 들고 다닐 필요가 없었다.

 

2. 이동 

- 20%정도에서 계속 틀렸다고 떴었다. 0이 다음으로 이동할 index 값을 찾는데서 오류가 있었다.

 

위 노란색 부분 ((index+1) % 3 == 0))에서 +1 (i == 1)로 이동하는 경우나, 초록색 부분 (index % 3 == 0) 에서 -1로 (i == 0)로 이동하는 경우는 배제되어야 한다. 0의 경우 next_index < 0 인 경우에서 걸러지게 된다.