[백준] 3041번 : N-퍼즐 - JAVA

 

백준 3041

 
 

개요

퇴근할 때쯤 디자이너 선임님께서 15퍼즐이라는 문제와 해당 문제를 풀 때 사용하는 A-Star 알고리즘을 알고 있냐고 물어봤다.
 
처음 들어봐서 공부도 할 겸 백준에서 검색을 해보니 비슷한 문제가 나와서 위 문제를 풀려고 했는데 뭔가 이상했다.
 
문제를 읽었을 때는 선임님에게 들은 내용(퍼즐이 움직이는 것)과 다르게 단순히 각 정사각형이 이동해야 하는 거리만 계산하면 해결되는 문제라고 느꼈지만... 이것도 이 문제와 인연이겠지 하면서 그냥 풀었다.
 
 

풀이

퍼즐에서 각 정사각형 문자와 'A' 문자를 빼서 얻은 정수는 다음과 같다.

[ 각 문자 - 'A' 값 ]
A: 0
B: 1
C: 2
...
O: 14

이렇게 보면 현재 위치에 있는 숫자를 4로 나눈 값이 x이고 4로 나눈 나머지 값이 y인 규칙이 하나 보인다.
 
현재 위치 숫자 11이 0,2 위치에 있다고 생각하면 원래 위치는 2,3인 것을 알 수 있다.
 
2 = 11 / 4 
3 = 11 % 4
 
 
이제 입력받은 문자의 현재 위치와 원래 위치를 알고 있으니 맨해튼 거리 공식을 사용하여 두 점 사이의 거리를 계산하면 해당 문제가 해결된다.

# 맨해튼 거리 공식은 두 점 사이의 거리를 측정하는 공식이며 이동을 수직 또는 수평 방향으로 이동하는 경우에만 적용이 가능하다.

# 맨해튼 거리 공식: D = |x1 - x2| + |y1 - y2|

 
 

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int PUZZLE_INDEX = 4;
        int answer = 0;

        for (int i = 0; i < PUZZLE_INDEX; i++) {
            String input = br.readLine();

            for (int ii = 0; ii < PUZZLE_INDEX; ii++) {
                char current = input.charAt(ii);

                if(current == '.') continue;

                int number = current - 'A';

                int x = number / 4;
                int y = number % 4;

                // 각 입력받은 정사각형의 위치와 원래의 위치 거리를 계산한다.
                answer += Math.abs(i - x) + Math.abs(ii - y);
            }
        }

        System.out.println(answer);
        br.close();
    }
    
}

 
 
 
A-Star 알고리즘에 대해 찾아보니 다익스트라 알고리즘에서 더 확장된 알고리즘으로 휴리스틱(비용 추정) 함수를 잘 설정하는 것이 중요하다고 하는데 다음에 해당 알고리즘을 사용하는 문제를 찾아서 풀어봐야겠다.