알고리즘
백준 2178 : 미로 탐색
Aye Bye Eye
2020. 8. 10. 18:15
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
|
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
|
#include <iostream>
#include <string>
#include <vector>
#include <queue>
struct coord
{
int y;
int x;
};
int N, M;
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int ans = 987654321;
int maze[100][100];
void input()
{
std::cin >> N >> M;
for (int y = 0; y < N; ++y)
{
for (int x = 0; x < M; ++x)
{
scanf("%1d", &maze[y][x]);
maze[y][x] = -maze[y][x];
}
}
}
void pf()
{
std::cout << '\n';
for (int y = 0; y < N; ++y)
{
for (int x = 0; x < M; ++x)
{
std::cout << maze[y][x] << ' ';
}
std::cout << '\n';
}
}
bool border_check(int y, int x)
{
return (-1 < y && -1 < x) && (y < N&& x < M);
}
void solve()
{
std::queue<coord> bfsQueue;
bfsQueue.push({ 0, 0 });
maze[0][0] = 1;
while (bfsQueue.empty() == false)
{
//pf();
coord pos = bfsQueue.front();
if (pos.y == N - 1 && pos.x == M - 1)
{
return;
}
bfsQueue.pop();
for (int i = 3; i >= 0; --i)
{
if (border_check(dy[i] + pos.y, dx[i] + pos.x) && maze[dy[i] + pos.y][dx[i] + pos.x] != 0)
{
//if (maze[dy[i] + pos.y][dx[i] + pos.x] == -1 || maze[pos.y][pos.x] < maze[dy[i] + pos.y][dx[i] + pos.x])
if (maze[dy[i] + pos.y][dx[i] + pos.x] == -1)
{
maze[dy[i] + pos.y][dx[i] + pos.x] = maze[pos.y][pos.x] + 1;
bfsQueue.push({ dy[i] + pos.y, dx[i] + pos.x });
}
}
}
}
}
void output()
{
std::cout << maze[N - 1][M - 1];
}
int main()
{
input();
solve();
output();
return 0;
}
|
cs |
BFS는 너비 우선이기 때문에 겉에서부터 얕게 깐다는걸 필히 마음속에 새겨놔야 한다
즉, 목적된 값을 찾는다면 그 값이 바로 어떠한 거리의 최솟값인 경우가 태반이기 때문에
다른 조건이 구태여 의미가 없어지는 경우가 생긴다
69번 라인의 저 주석처럼..