[백준] 1525번 퍼즐(java)

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

1525번: 퍼즐

bfs를 이용하여 풀 수 있다.

 

 

핵심

2차원 배열을 일렬로 두고 그 값자체를 가지고 판단하면 편하게 구할 수 있다.

값의 위치를 바꿀 때 각각의 index를 알아야 하는데, 이때 StringBuilder를 이용하면 쉽게 위치를 바꿀 수 있다.

StringBuilder.setCharAt -> 특정 위치에 char를 삽입할 수 있다.

이를 활용하여 풀어보자.

 

 

정답 코드

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int value = 0;
        for (int i = 0; i < 9; i++){
            int v = sc.nextInt();
            if (v==0)v = 9;
            value = (value*10) + v;
        }

        Map<Integer, Integer> map = new HashMap<>();
        Queue<Integer> q = new LinkedList<>();
        map.put(value,0);
        q.offer(value);

        int[] dy = {1,0,-1,0};
        int[] dx = {0,-1,0,1};
        while (!q.isEmpty()){
            int nowNum = q.poll();
            String now = String.valueOf(nowNum);
            int nineIndex = now.indexOf("9");
            int y = nineIndex/3;
            int x = nineIndex%3;
            for (int i = 0; i < 4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];
                int move = ny*3+nx;
                if (0<= ny && ny <3 && 0<= nx && nx <3){
                    StringBuilder sb = new StringBuilder(now);
                    char temp = sb.charAt(move);
                    sb.setCharAt(move,'9');
                    sb.setCharAt(nineIndex,temp);
                    int next = Integer.parseInt(sb.toString());
                    if (!map.containsKey(next)){
                        map.put(next, map.get(nowNum)+1);
                        q.offer(next);
                    }
                }
            }
        }
        if (map.containsKey(123456789)) {
            System.out.println(map.get(123456789));
        } else {
            System.out.println(-1);
        }
    }
}

해설

입력받은 값을 일렬로 두기 위해 value를 1칸씩 늘렸다. -> value = value*10 + v;

또한 이미 바꾼 적 있는 조합은 만들 필요가 없고, 각각의 카운트를 위해 map을 사용하였다.

bfs를 하기 위해 Queue를 선언하였다.

현재 담겨있는 값에서 9의 위치를 가져온다.

그 위치를 가지고 현재 x, y좌표를 구하고, 해당 좌표에서 이동하는 한 위치를 찾는다.

바꿀 수 있다면, 그 위치에 해당하는 문자와 원래 9가 있던 문자의 위치를 바꾼다.

이때 StringBuilder.setCharAt()을 사용하면 쉽게 바꿀 수 있다.

이미 map에 해당 값이 존재하면 값을 넣지 않는다.

마지막으로 우리가 원하는 123456789가 있는지 확인 후 출력한다.

 

 

배운 점

이 문제를 보고, 처음에는 감도 잡지 못하였다.

이러한 문제는 처음 풀어보았고, 보자마자 아이디어가 떠오르지 않았다.

풀이를 보니 어느 정도 생각할만한 부분도 있었다. Map을 사용하여 bfs를 하니 새로운 경험이었다.

또한 StringBuilder의 메서드를 활용할  수 있어서 새로웠다.