Newer
Older
---
layout : wiki
title : BOJ 1525. 퍼즐
summary :
date : 2021-03-01 23:56:56 +0900
updated : 2021-12-15 18:26:34 +0900
tag :
public : true
published : true
parent : [[boj]]
latex : false
---
* TOC
{:toc}
## 1 번째 시도
- 언제 했는지 모르겠다. 코드가 엉망이다.
## 2 번째 시도
- 최소 이동 횟수를 구해야하기 때문에 bfs를 떠올렸다.
- 각 3x3 배열의 상태와 함께 0의 위치를 알아야 했기에 0의 위치 r, c와 3x3배열을 갖는 Node class를 만들고, 해당 class를 queue에 넣었다.
- 3x3 배열의 방문 형태는 3x3 배열을 일렬로 나열한 모습의 String으로 하였고, 자료구조 Set으로 방문 여부를 판단하였다.
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
static class Node {
int r, c;
int[][] board;
Node(int r, int c , int[][] board) {
this.r = r;
this.c = c;
this.board = new int[3][3];
copyBoard(board, this.board);
}
}
static void copyBoard(int[][] src, int[][] dest) {
for (int i = 0; i < 3; i++)
System.arraycopy(src[i], 0, dest[i], 0, 3);
}
static void swap(int[][] arr, int r1, int c1, int r2, int c2) {
int tmp = arr[r1][c1];
arr[r1][c1] = arr[r2][c2];
arr[r2][c2] = tmp;
}
static Set<String> visited = new HashSet<>();
static int[][] input = new int[3][3];
static int sr, sc;
static int[] dx = {-1 , 0, 1, 0};
static int[] dy = { 0 ,-1, 0, 1};
static int bfs() {
Queue<Node> q = new ArrayDeque<>();
q.offer(new Node(sr, sc, input));
int cnt = 0;
while (!q.isEmpty()) {
int qSize = q.size();
for (int qs = 0; qs < qSize; qs++) {
Node cur = q.poll();
boolean isFin = true;
for (int i = 0; i < 8; i++)
if (cur.board[i/3][i%3] != i+1)
isFin = false;
if(isFin) return cnt;
for (int i = 0; i < 4; i++) {
int nr = cur.r + dx[i];
int nc = cur.c + dy[i];
if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3)
continue;
int[][] nextBoard = new int[3][3];
copyBoard(cur.board, nextBoard);
swap(nextBoard, cur.r, cur.c, nr, nc);
StringBuilder sb = new StringBuilder();
for (int j = 0; j < 9; j++)
sb.append(nextBoard[j/3][j%3]);
if (visited.contains(sb.toString()))
continue;
visited.add(sb.toString());
q.offer(new Node(nr, nc, nextBoard));
}
}
cnt++;
}
return -1;
}
```