문제
풀이
DFS를 이용하여 코드를 작성하면, 완전 탐색을 통해 얻어낸 경로 중 최단값을 채택해야된다. 그로 인해 시간초과를 면할 수가 없다. 최단 거리 문제는 보통 BFS를 이용한다고 한다. BFS를 이용해서 상하좌우 근접해 있는 경로를 지날 때 마다 가중치 + 1을 하여 코드를 작성하면 최단경로를 효율적으로 만들 수 있다. 코드는 DFS와 BFS 기본 코드에서 크게 벗어나지 않는다.
소스 코드
** DFS(시간 초과) **
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
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<vector<int>> map(101, vector<int> (101));
vector<vector<bool>> visit(101, vector<bool> (101));
int N, M;
int cnt;
int result_cnt = INT_MAX;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
void dfs(int y, int x, int cnt){
if(y == N && x == M){
result_cnt = min(cnt, result_cnt);
visit[y][x] = false;
return;
}
for(int i = 0; i<4; i++){
if(y+dy[i] <= N && y+dy[i] >=1 && x+dx[i] >=1 && x+dx[i] <= M){
if(map[y+dy[i]][x+dx[i]] == 1 && visit[y+dy[i]][x+dx[i]] == false){
visit[y][x] = true;
cnt++;
dfs(y+dy[i], x+dx[i], cnt);
visit[y][x] = false;
cnt--;
}
}
}
}
int main(){
scanf("%d %d", &N, &M);
for(int i = 1; i<=N; i++){
for(int j = 1; j<=M; j++){
scanf("%1d", &map[i][j]);
}
}
dfs(1, 1, 1);
printf("%d\n", result_cnt);
}
** BFS **
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
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
vector<vector<int>> map(101, vector<int> (101));
vector<vector<bool>> visit(101, vector<bool> (101));
vector<vector<int>> check(101, vector<int> (101));
int N, M;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
void bfs(int y, int x){
queue<pair<int, int>> q;
visit[y][x] = true;
q.push(make_pair(y, x));
while(!q.empty()){
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 0; i<4; i++){
if(y+dy[i] <= N && y+dy[i] >= 1 && x+dx[i] <= M && x+dx[i] >=1 && visit[y+dy[i]][x+dx[i]] == false && map[y+dy[i]][x+dx[i]] == 1){
visit[y+dy[i]][x+dx[i]] = true;
q.push(make_pair(y+dy[i], x+dx[i]));
check[y+dy[i]][x+dx[i]] = check[y][x] + 1;
}
}
printf("loop\n");
}
}
int main(){
scanf("%d %d", &N, &M);
for(int i = 1; i<=N; i++){
for(int j = 1; j<=M; j++){
scanf("%1d", &map[i][j]);
}
}
bfs(1, 1);
printf("%d\n", check[N][M] + 1);
}
