BOJ_1525_퍼즐

백준 1525 퍼즐 문제는 큐를 이용한 BFS와 HashMap을 사용한 문제이다.

보통 큐를 이용한 BFS를 풀기 위해선 다음 조건이 따른다.

1. 노드간 이어지는 간선의 가중치는 모두 다 1이다.

2. 최소한의 경로로 탐색하려고 한다.

이 두 조건이 붙고 문제 풀이는 다음과 같다.

1. 노드 간에 이동을 하였는지 알아보기 위해서 boolean 배열을 사용한다.

예를 들어, 1번 노드에서 2번 노드로 이동할 때 이미 2번 노드로 이동하는 간선을 사용했다면,

boolean[] visit = new boolean[10001];

visit[1] = true; ( 1번 노드에서 2번 노드로 이동하는 1번 간선을 이미 사용했다. )

이런 식으로 이미 이동했으니 이동할 수 없다는 boolean 배열로 만들어준다.

2. Queue를 만든다.

보통은 계산을 편리하게 하기 위해서 노드를 숫자로 만들고 그 노드들을 담을 큐 또한

자료형을 Integer로 선언하여 만든다.

그래서 처음 시작점을 큐에 넣고 이동을 시작하는데, 처음 큐에 있는 값은 remove(), poll() 등으로 뽑아내어서

연산을 시작한다.

연산된 결과 , 즉 노드를 이동하여 다음 노드에 도착했을 때에 해당 값을 큐에 넣어준다.

반복문은 큐가 비어있지 않을 경우까지 돌도록 알고리즘을 짜준다.

3. 노드 간 이동한 것을 계산할 배열을 만든다.

이는 결과 값을 출력하기 위해서 만드는 배열로 노드간 이동에 대해 가중치가 모두 1이기 때문에 가능한 방법이다.

물론 가중치를 다르게 할 경우 그 만큼 계산해서 더해주면 되지만 보통은 가중치가 1로 계산 되어서 

문제가 제공되기 때문에 다음과 같은 방법을 사용하면 된다.

int[] dist = new int[10001];

while(!queue.isEmpty()){

for(int i=0;i<배열의 길이;i++){

int next = (for문을 통해서 위치가 변경될 내용의 함수를 따로 만들어서 정리해주면 된다. --> 보통은 값 끼리 자리 바꿈 하는 정도로 진행 된다.)

if(!visit[i]){

// i 노드에 방문하지 않았을 경우

// 현재 노드 위치에서 + 1 한 값이 다음 노드 위치에서의 값 (이동 얼마나 했는지 체크하기 위함)

dist[next] = dist[now] + 1; 

}

}

다음과 같은 방법으로 진행된다.

하지만 이와는 다르게 1525번 문제인 퍼즐은 큐를 사용하여 풀었고, 방문 여부를 묻지 않았다. 

문제부터 파악해보자.

---

---

여기서 포인트는 어떻게 문제를 쉽게 만드냐는 것이다.

2차원 배열은 너무 어렵지만 이를 1차원 배열, 더 나아가 문자열로 만든다면 얼마나 쉬울까?

1 0 3

4 2 5

7 8 6 

이것을 이렇게 바꿔보자 

1 0 3 4 2 5 7 8 6 

또 이것을 이렇게 바라봐야 한다.

(1 0 3) (4 2 5) (7 8 6)

행으로 나눈 그룹이다. 그리고 2차원 배열이기 때문에 자연스럽게 반복문을 두 개 중첩에서 시간복잡도 n^2을 생각할 것이다.

반복문 두 개이기 때문에 외부 반복문은 행이되고, 내부 반복문은 열이될텐데, 그 차이가 3*3 배열이므로

3만큼 차이날 것이다. (행이)

따라서 (1 0 3) 그룹에서 (4 2 5) 그룹으로 이동하기 위해서는 *3만큼 이동해야 한다는 것이다.

(행 간의 이동을 하기 위해서)

그리고 내부의 반복문에선 열을 나타내기 때문에 3만큼의 범위 내에서 더하기만 해주면 된다. 

추가로 좀 더 머리를 쓰자면, 행이 3의 몫이 되고, 열이 3의 나머지가 된다고 말할 수 있다.

그리고 1 0 3 4 2 5 7 8 6 이것을 하나의 숫자로 만들고 이를 문자열로 바꾸기 위해선 다음과 같은 센스가 필요하다.

---

int start = 0;

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

int tmp = scanner.nextInt(); // 숫자 넣어주기

if (tmp == 0)

tmp = 9;

start = start * 10 + tmp; // 자릿수 한 칸씩 이동해야하므로 *10을 해준 것입니다.

}

}

---

10진수이기 때문에 자리 이동간에는 *10 만큼 이동하고 1~9 사이의 값을 더해주면 그 만큼의 크기 값이 나오게 된다.

그리고 이동 중에는 상하,좌우 개념이 있어야 하므로 이동할 수 있는 배열을 만든다. 

이 또한 이동 중 가중치가 1이기 때문에 BFS로 생각할 수 있다.

private static int[] dx = { 1, -1, 0, 0 };

private static int[] dy = { 0, 0, 1, -1 };

이제 BFS 방법으로 접근한다.

큐에 처음 시작점을 넣어준다. 

그리고 맵을 이용해서 시작점(KEY)에 대한 값을 0으로 먼저 넣어준다.

그리고 나서 앞서 말했듯이, 큐가 비어 있지 않을 경우 반복문을 계속 돌릴 수 있도록 진행한다.

문제에서는 9의 위치를 이동하면서 우측 하단으로 옮기는 것이기 때문에 

9의 인덱스 값을 구해서 x,y 값을 구한다.

구한 x,y 값에 dx , dy 배열 값을 더해줘서 이동시킨다.

그리고 이동한 x,y에 대해서 이동 전 x,y의 위치의 값과 변경해준다. (swap)

그 후에 큐에 이동한 노드의 값을 넣어주고 마찬가지로 맵에도

이동한 노드의 값을 KEY로 주면서 처음 시작점을 KEY로 갖는 값을 가지고 온다. (처음에 0을 넣어주었음)

그래서 해당 값을 +1 씩 해주면서 처음 노드에서 얼마나 이동해야 목적지 까지 가는지 확인한다.

반복문 이 후에 마지막에는 맵에 해당 값이 있는지 체크하고 있을 경우 이동한 거리, 

즉, 맵에서의 start 키 값을 불러오면 된다.

코드는 다음과 같다.

---

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class 퍼즐_순열 {

private static Scanner scanner;

private static int[] dx = { 1, -1, 0, 0 };

private static int[] dy = { 0, 0, 1, -1 };

private static Queue<Integer> queue;

private static int[] dist;

private static final int MAX = 10001;

private static String puzzleAns;

private static HashMap<Integer, Integer> map;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int start = 0;

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

int tmp = scanner.nextInt(); // 숫자 넣어주기

if (tmp == 0)

tmp = 9;

start = start * 10 + tmp; // 자릿수 한 칸씩 이동해야하므로 *10을 해준 것입니다.

}

}

queue = new LinkedList<>();

map = new HashMap<Integer, Integer>();

queue.add(start);

map.put(start,0);

// 처음 시작 점을 큐에 넣고 이동을 시킨다.

// 193 / 425 / 786 (이렇게 나눠서 볼 수 있는데 i가 0일땐 193 라인, 1일떈 425 라인, 2일땐 786 라인입니다.

// j는 각 그룹의 요소들을 접근할 수 있다. 예를들어, i*3+j인데 i가 1이고 j가 2라면 답은 5가 나올 것이다.

while (!queue.isEmpty()) {

// 9가 나오는 위치를 찾아서 위치를 찾고 해당 위치를 기준으로 x,y의 위치를 찾는다.

// x,y의 위치를 찾은 뒤에 그 인덱스로 9의 값을 이동시킨다.

// 이동시키면서 9가 우측 하단으로 갈 수 있도록 계속해서 swap해준다.

int nowNum = queue.remove(); // 현재 있는 위치의 숫자 : 193425786

String now = String.valueOf(nowNum); // 193425786을 문자열로 만든 뒤에 여기서 9를 찾는다.

int nine = now.indexOf('9'); // 9가 있는 곳의 인덱스를 찾는다.

int x = nine / 3;

int y = nine % 3;

for (int i = 0; i < 4; i++) {

int nx = x + dx[i];

int ny = y + dy[i];

if ((nx >= 0 && nx < 3) && (ny >= 0 && ny < 3)) {

// 범위 내에 있어야함

/*

* 이제 해야할 것은 다음 가야할 노드를 찾는다. 3*x + y 일 때의 값과 nx*3 + ny의 값을 위치 변경해줘야합니다.

* 

*/

StringBuilder next = new StringBuilder(now); // 현재 위치의 문자열 값을 StringBuilder를 통해서 만든다.

char temp = next.charAt(x * 3 + y); // 이 전에 있던 것을 temp에 넣어두고 (해당 인덱스가 있는 값임)

next.setCharAt(x * 3 + y, (char) next.charAt(nx * 3 + ny)); // nx*3+ny의 인덱스를 갖는 값이 나오게 된다.

next.setCharAt(nx * 3 + ny, temp); // nx*3+ny의 인덱스 쪽에 temp(x*3+y)의 인덱스를 갖는 곳의 값을 넣어서 넘겨준다.

// 변경하였고 이 next를 queue에 넣어주고 Map의 키에다가도

int num = Integer.parseInt(next.toString());

if (!map.containsKey(num)) {

map.put(num, map.get(nowNum) + 1);

queue.add(num);

}

}

}

}

if(map.containsKey(123456789)) {

System.out.println(map.get(123456789));

}else {

System.out.println("-1");

}

}

}

---