[JAVA] BOJ 백준 1525번 - 퍼즐

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1525번: 퍼즐

---

2. 내가 푼 방법

메모리가 32MB인게 제일 먼저 보여서 방문한 노드를 확인하기 위한 boolean[] visit = new boolean[876543210]; 에 대한 선언을 시도해 봤는데 실패했다. 따라서 다른 분들의 풀이를 통해 Map 자료구조를 이용하는 것을 참고했다.

 

나는 PriorityQueue를 사용했는데, 그래서 Set을 통해 이미 방문한 적 있는 노드인지 확인했다.

어차피 최소 이동 횟수를 가진 문자열이 먼저 확인되기 때문에 Set 자료구조와 contains를 이용했다.

public static void solution() {
    PriorityQueue<Tuple> queue = new PriorityQueue<>();
    queue.add(new Tuple(startNum, 0));

    while (!queue.isEmpty()) {
        Tuple t = queue.poll();
        String num = t.num;
        int cnt = t.cnt;

        if (visit.contains(num)) continue;
        if (num.equals(makeMapArr)) {
            result = cnt;
            break;
        }

        visit.add(num);

        int zeroIndex = num.indexOf("0");
        int x = zeroIndex / N;
        int y = zeroIndex % N;

        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;

            int nextIndex = nextX * N + nextY;
            StringBuilder sb = new StringBuilder(num);
            sb.setCharAt(zeroIndex, num.charAt(nextIndex));
            sb.setCharAt(nextIndex, num.charAt(zeroIndex));

            queue.add(new Tuple(sb.toString(), cnt+1));
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1525.java

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static String startNum;
    static Set<String> visit;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static String makeMapArr = "123456780";
    static int result;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        PriorityQueue<Tuple> queue = new PriorityQueue<>();
        queue.add(new Tuple(startNum, 0));
    
        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            String num = t.num;
            int cnt = t.cnt;
    
            if (visit.contains(num)) continue;
            if (num.equals(makeMapArr)) {
                result = cnt;
                break;
            }
    
            visit.add(num);
    
            int zeroIndex = num.indexOf("0");
            int x = zeroIndex / N;
            int y = zeroIndex % N;
    
            for (int i = 0; i < 4; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];
    
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;
    
                int nextIndex = nextX * N + nextY;
                StringBuilder sb = new StringBuilder(num);
                sb.setCharAt(zeroIndex, num.charAt(nextIndex));
                sb.setCharAt(nextIndex, num.charAt(zeroIndex));
    
                queue.add(new Tuple(sb.toString(), cnt+1));
            }
        }
    }

    public static class Tuple implements Comparable<Tuple> {
        String num;
        int cnt;

        public Tuple(String num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Tuple t) {
            return this.cnt - t.cnt;
        }
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = 3;
        startNum = "";
        visit = new HashSet<>();
        result = -1;

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                startNum += st.nextToken();
            }
        }

        br.close();
    }
}

---

4. 풀이 및 회고

 

위에 제출한 코드가 Set을 이용한거고, 아래가 Map으로 작성한 코드였는데 시간은 아주 조금 단축이 됐네ㅎㅎ