1525번: 퍼즐
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
www.acmicpc.net
3 * 3 퍼즐을 이동시켜서 위와같은 상태로 만들고, 이동의 최소 횟수를 출력하고, 불가능한 경우 -1를 출력합니다.
저는 3 * 3 퍼즐을 String으로 변환시켰습니다.
1 0 3
4 2 5
7 8 6입력이 이렇게 주어지면 "103425786"을 만든 다음 bfs를 돌렸습니다. (방문체크도 Set<String>으로 하였습니다.)
그리고 각 칸에서 움직일 수 있는 공간을 ArrayList배열을 만들어서 모두 만들어줍니다.
왼쪽 위 칸 번호가 0번부터 시작해서 오른쪽 아래 칸 번호가 8번이되어
0 -> 1, 3
1 -> 0, 2, 4
2 -> 1, 5
3 -> 0, 4, 6
4 -> 1, 3, 5, 7
5 -> 2, 4, 8
6 -> 3, 7
7 -> 4, 6, 8
8 -> 5, 7
이렇게 그래프를 연결시킬 수 있습니다.
이제 bfs를 돌려줍니다.
덱에 입력받은 문자열(str), 0의 위치(idx), 움직인 횟수(cnt)를 넣어줍니다.
bfs 과정에서는 현재 문자열에서 idx위치와 next위치의 문자열을 서로 바꿔줍니다.
그리고 중복체크를 하고, 덱에 넣어주는 방식으로 하였습니다.
덱에서 꺼낸 문자열이 ans인 "123456780"과 같으면 cnt를 출력하고 리턴합니다.
만약 ans와 같은 문자열이 나오지 않았는데 덱이 비어있게되면 "123456780"을 만들수 없으므로 -1을 출력합니다.
[C++]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
96
97
98
99
100
101
102
103
104
105
106
|
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
using namespace std;
typedef struct list {
string now;
int idx;
int cnt;
}list;
queue<list> q;
set<string> s;
vector<int> v[9];
string ans = "123456780", str = "";
void init() {
v[0].push_back(1);
v[0].push_back(3);
v[1].push_back(0);
v[1].push_back(2);
v[1].push_back(4);
v[2].push_back(1);
v[2].push_back(5);
v[3].push_back(0);
v[3].push_back(4);
v[3].push_back(6);
v[4].push_back(1);
v[4].push_back(3);
v[4].push_back(5);
v[4].push_back(7);
v[5].push_back(2);
v[5].push_back(4);
v[5].push_back(8);
v[6].push_back(3);
v[6].push_back(7);
v[7].push_back(4);
v[7].push_back(6);
v[7].push_back(8);
v[8].push_back(5);
v[8].push_back(7);
}
void bfs() {
while (!q.empty()) {
string now = q.front().now;
int idx = q.front().idx;
int cnt = q.front().cnt;
q.pop();
if (!now.compare(ans)) {
cout << cnt << '\n';
return;
}
for (int i = 0; i < v[idx].size(); i++) {
int next = v[idx][i];
string tmp = now;
swap(tmp[idx], tmp[next]);
if (s.find(tmp) != s.end()) continue;
q.push({ tmp, next, cnt + 1 });
s.insert(tmp);
}
}
cout << "-1\n";
}
void input() {
int k = 0;
string tmp = "";
for (int i = 0; i < 9; i++) {
cin >> tmp;
str += tmp;
if (tmp[0] == '0') {
k = i;
}
}
q.push({ str, k, 0 });
s.insert(str);
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
input();
bfs();
return 0;
}
|
cs |
[Java]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
static class Pair {
String now;
int idx;
int cnt;
public Pair(String now, int idx, int cnt) {
this.now = now;
this.idx = idx;
this.cnt = cnt;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static String ans = "123456780";
static ArrayList<Integer> list[] = new ArrayList[9];
static String str = "";
static void init() {
for (int i = 0; i < 9; i++)
list[i] = new ArrayList<>();
list[0].add(1);
list[0].add(3);
list[1].add(0);
list[1].add(2);
list[1].add(4);
list[2].add(1);
list[2].add(5);
list[3].add(0);
list[3].add(4);
list[3].add(6);
list[4].add(1);
list[4].add(3);
list[4].add(5);
list[4].add(7);
list[5].add(2);
list[5].add(4);
list[5].add(8);
list[6].add(3);
list[6].add(7);
list[7].add(4);
list[7].add(6);
list[7].add(8);
list[8].add(5);
list[8].add(7);
}
static void bfs() {
Set<String> s = new HashSet<>();
Deque<Pair> dq = new ArrayDeque<>();
dq.add(new Pair(str, str.indexOf("0"), 0));
s.add(new String(str));
while (!dq.isEmpty()) {
String now = dq.peek().now;
int idx = dq.peek().idx;
int cnt = dq.poll().cnt;
if (now.equals(ans)) {
System.out.println(cnt);
return;
}
for (int i = 0; i < list[idx].size(); i++) {
int next = list[idx].get(i);
char newstr[] = new String(now).toCharArray();
char tmp = newstr[idx];
newstr[idx] = newstr[next];
newstr[next] = tmp;
String s1 = String.valueOf(newstr);
if (s.contains(s1))
continue;
dq.add(new Pair(s1, next, cnt + 1));
s.add(new String(s1));
}
}
System.out.println(-1);
}
static void input() throws Exception {
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
str += st.nextToken();
}
}
}
public static void main(String[] args) throws Exception {
init();
input();
bfs();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 11559 Puyo Puyo (0) | 2021.02.26 |
|---|---|
| boj 15653 구슬 탈출 4 (0) | 2021.02.22 |
| boj 7576 토마토 (0) | 2021.02.19 |
| boj 17135 캐슬 디펜스 (0) | 2021.02.17 |
| boj 16236 아기 상어 (0) | 2021.02.14 |