알고리즘
- BFS로 하나씩 찾아갈 수 있지만, 나는 연결되어있는 타일을 그래프로 표현한 다음 BFS를 하였다.
- BFS를 할땐, visit을 -1로 초기화하고, 이전에 온 곳을 기록하는 형식으로 하자.
- 그러면 마지막에서부터 온곳을 탐색하며 가서 첫번째 타일까지 가면 된다.
코드
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
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
using namespace std;
int N, tile[250000][2], last, visit[250000];
vector<int> graph[250000], path;
list<int> l;
void makeGraph();
void bfs();
int main() {
cin >> N;
last = N * N - N / 2;
for (int i = 1; i <= last; i++)
cin >> tile[i][0] >> tile[i][1];
makeGraph();
memset(visit, -1, sizeof(visit));
bfs();
cout << path.size() << endl;
for (int j = path.size() -1; j >=0; j--)
cout << path[j] << " ";
}
void makeGraph() {
for (int i = 1; i <= N; i++) {
int end, start;
if (i % 2 == 0) { // 짝수줄
end = N - 1;
start = N * (i / 2) + (N - 1) * ((i / 2) - 1);
}
else { // 홀수줄
end = N;
start = N * (i / 2) + (N - 1) * (i / 2);
}
// 좌우, +-N, +-(N-1), 이때 홀수번째 처음은 +N-1, -N 안되고, 마지막은 +N, -N-1 안됨
for (int j = start + 1; j <= start + end; j++) {
if (j != start + 1 || i % 2 == 0) { // 왼쪽
if (tile[j - 1][1] == tile[j][0] && j != start + 1)
graph[j].push_back(j - 1);
if (j - N >= 1 && tile[j - N][1] == tile[j][0]) // -N
graph[j].push_back(j - N);
if (j + N - 1 <= last && tile[j + N - 1][1] == tile[j][0]) // +N-1
graph[j].push_back(j + N - 1);
}
if (j != start + end || i % 2 == 0) { // 오른쪽
if (tile[j + 1][0] == tile[j][1] && j != start + end)
graph[j].push_back(j + 1);
if (j - N + 1 >= 1 && tile[j - N + 1][0] == tile[j][1]) // -(n-1)
graph[j].push_back(j - N + 1);
if (j + N <= last && tile[j + N][0] == tile[j][1]) // + N
graph[j].push_back(j + N);
}
}
}
}
// 다익스트라 후 검증으로 길찾기
void bfs() {
visit[1] = 0;
l.push_back(1);
while (!l.empty()) {
int cur = l.front();
l.pop_front();
for (int i = 0; i < graph[cur].size(); i++) {
int next = graph[cur][i];
if (visit[next] == -1) {
visit[next] = cur;
l.push_back(next);
}
}
}
int first = 0;
for (int i = last; i >= 1; i--) {
if (visit[i] != -1) {
first = visit[i];
path.push_back(i);
break;
}
}
int cur = first;
while (cur != 0) {
path.push_back(cur);
cur = visit[cur];
}
return;
}