문제 링크 : https://www.acmicpc.net/problem/17070
이 문제는 목적지까지의 최단거리도 아닌, 그리고 목적지까지 가는데 걸리는 최소 시간도 아닌 가는 방법의 개수를 묻는 문제 입니다.
이 문제를 해결하기 위해 BFS를 사용할지, DFS(즉, 완전탐색)을 사용할지 고민을 하였습니다. 하지만 결론은 "BFS를 사용하자" 입니다.
그 이유는, BFS로 하게될 경우 방문 여부가 달린 visited 배열을 매 루프당 할당해주어야 하는데( 혹은 pair로 저장할 수 있겠습니다) 이 경우 메모리 초과가 우려되었습니다.
따라서 BruteForce 방식으로 풀게 되었습니다.
이 문제는 기초 완전탐색 문제와는 약간 다르게, 직전에 어떤 방법으로 중간 기착지에 도달했느냐에 따라 현재의 이동 방법이 제한됩니다.
직전에 가로로 이동하였을 경우, 현재는 세로로 이동하지 못하고 대각선 혹은 가로로 이동하여야 합니다. 이를위해 prev 매개변수를 만들어서 제한을 두었습니다. 이 외에는, 완전탐색 알고리즘과 동일합니다.
소스코드 :
이 문제는 목적지까지의 최단거리도 아닌, 그리고 목적지까지 가는데 걸리는 최소 시간도 아닌 가는 방법의 개수를 묻는 문제 입니다.
이 문제를 해결하기 위해 BFS를 사용할지, DFS(즉, 완전탐색)을 사용할지 고민을 하였습니다. 하지만 결론은 "BFS를 사용하자" 입니다.
그 이유는, BFS로 하게될 경우 방문 여부가 달린 visited 배열을 매 루프당 할당해주어야 하는데( 혹은 pair로 저장할 수 있겠습니다) 이 경우 메모리 초과가 우려되었습니다.
따라서 BruteForce 방식으로 풀게 되었습니다.
이 문제는 기초 완전탐색 문제와는 약간 다르게, 직전에 어떤 방법으로 중간 기착지에 도달했느냐에 따라 현재의 이동 방법이 제한됩니다.
직전에 가로로 이동하였을 경우, 현재는 세로로 이동하지 못하고 대각선 혹은 가로로 이동하여야 합니다. 이를위해 prev 매개변수를 만들어서 제한을 두었습니다. 이 외에는, 완전탐색 알고리즘과 동일합니다.
소스코드 :
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
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cmath>
#include <map>
#include <cstdlib>
#include <ctime>
#include <map>
using namespace std;
int dy[3] = { 1, 0, 1 };
int dx[3] = { 0,1,1 };
int n;
int cnt = 0;
void BruteForce(int y, int x, vector<vector<int> > & v, vector<vector< bool> > & visited, int prev) {
if (y == n && x == n) {
cnt++;
return;
}
if (y < 1 || y > n || x < 1 || x > n) {
return;
}
for (int i = 0; i < 3; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if ((prev == 0 && i == 1) || (prev == 1 && i == 0))
continue;
if (!visited[ny][nx] && v[ny][nx] == 0 && ny <= n && nx <= n){
visited[ny][nx] = true;
if (i == 2) {
if (v[ny - 1][nx] == 0 && v[ny][nx - 1] == 0) {
BruteForce(ny, nx, v, visited, i);
}
}
else {
BruteForce(ny, nx, v, visited, i);
}
visited[ny][nx] = false;
}
}
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> n;
vector<vector<int> > v(n + 2, vector<int>(n + 2));
vector<vector<bool> > visited(n + 2, vector<bool>(n + 2));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> v[i][j];
}
}
visited[1][1] = true;
visited[1][2] = true;
BruteForce(1, 2, v, visited, 1);
cout << cnt << endl;
}
| cs |
댓글
댓글 쓰기