[백준] 1525. 퍼즐

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

1525번: 퍼즐

• 퍼즐에서 0의 위치를 찾아서 4방향(위, 아래, 왼쪽, 오른쪽)으로 bfs를 진행하면 된다.
• 그런데 해당 퍼즐을 이미 만들었다면 패스하는 로직을 작성해야 한다. 이때 이차원 배열로 비교하면 복잡하기 때문에 다음과 같이 문자열로 변경해서 생각하면 된다.
  • 1 2 3 
    4 5 6
    7 8 0
  • ➡️ 123456780
• 그리고 방문 여부뿐만 아니라 몇 번만에 해당 퍼즐을 만들었는지 저장해주어야 하는데 map을 사용하면 방문 여부와 횟수를 간편하게 저장할 수 있다. map의 key는 중복이 불가하므로 key에 퍼즐의 문자열을 담아주고, value에 몇 번만에 해당 문자열(퍼즐)을 만들었는지 기록하면 된다.
• 내가 가장 크게 실수한 부분은 다음과 같다.
  • 처음에 0의 위치를 위, 아래, 왼쪽, 오른쪽으로 이동하는 로직을 인덱스 -3, +3, -1, +1로 두어서 계산했었다.
  • 그런데 이렇게 하면 다음의 경우 문제가 발생한다. 0은 가장 오른쪽에 있기 때문에 오른쪽으로 이동할 수 없다. 그런데 내가 생각한 로직으로는 0과 3이 바뀌게 되는 문제가 발생한다. 
    • 1 2 0
      3 4 5
      6 7 8
  • 따라서 이 점에 주의해서 코드를 작성해주어야 한다. 올바르게 작성한 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Map<String, Integer> map = new HashMap<>();
    static Queue<String> que = new LinkedList<>();

    public static void main(String[] args) throws IOException {

        String start = "";
        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                start += Integer.parseInt(st.nextToken());
            }
        }

        // bfs
        map.put(start, 0); // 시작점은 누적 count가 0
        que.add(start);
        while (!que.isEmpty()) {
            String now = que.poll();

            if (now.equals("123456780")) {
                System.out.println(map.get(now));
                return;
            }

            int zeroIdx = now.indexOf("0");

            // 위와 바꾸기
            if (zeroIdx > 2) {
                int moveIdx = zeroIdx - 3;
                move(now, moveIdx);
            }

            // 아래와 바꾸기
            if (zeroIdx < 6) {
                int moveIdx = zeroIdx + 3;
                move(now, moveIdx);
            }

            // 오른쪽과 바꾸기
            if (zeroIdx != 2 && zeroIdx != 5 && zeroIdx != 8) {
                int moveIdx = zeroIdx + 1;
                move(now, moveIdx);
            }

            // 왼쪽과 바꾸기
            if (zeroIdx != 0 && zeroIdx != 3 && zeroIdx != 6) {
                int moveIdx = zeroIdx - 1;
                move(now, moveIdx);
            }
        }
        System.out.println(-1);
    }

    private static void move(String now, int moveIdx) {
        // 움직이기
        String newStr = new String(now);

        char moveNum = now.charAt(moveIdx);
        newStr = newStr.replace(moveNum, 'c');
        newStr = newStr.replace('0', moveNum);
        newStr = newStr.replace('c', '0');

        // 방문 여부 확인 후 방문 안했으면, 방문 처리(map) 후 큐에 넣기
        if (!map.containsKey(newStr)) {
            map.put(newStr, map.get(now) + 1);
            que.add(newStr);
        }
    }
}