반응형
문제
https://www.acmicpc.net/problem/2178
풀이
bfs 탐색을 (1,1)에서 시작해서 (N,M)에 도착했을 때 지나가는 level의 수가 최소 횟수가 된다.
result = (1,1)에서 (N,M)까지 이동할 때 지나야하는 최소 칸 수 라고 할 때,
bfs 탐색을 진행하면서 현재 level에 해당되는 좌표들을 모두 방문한 후에 result 값을 증가시켜주면 된다.
현재 level에 해당하는 좌표를 모두 방문하려면, 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
59
60
61
62
|
#include <iostream>
#include <queue>
using namespace std;
int N, M;
char graph[102][102];
bool visit[102][102];
int result;
pair<int, int> direction[4] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
void bfs()
{
queue<pair<int, int>> q;
q.push({1, 1});
visit[1][1] = true;
while(!q.empty())
{
int len = q.size();
while(len--)
{
int i=q.front().first, j=q.front().second; q.pop();
if (i == N && j == M)
{
result++;
return;
}
for (int l=0; l<4; l++)
{
int nextI = i + direction[l].first;
int nextJ = j + direction[l].second;
if (graph[nextI][nextJ]=='1' && !visit[nextI][nextJ])
{
q.push({nextI, nextJ});
visit[nextI][nextJ] = true;
}
}
}
result++;
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(0);
cin >> N >> M;
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++) cin >> graph[i][j];
bfs();
cout << result;
return 0;
}
|
cs |
반응형
'BOJ' 카테고리의 다른 글
백준 10815 - 숫자 카드 (0) | 2019.09.22 |
---|---|
백준 2146 - 다리 만들기 (1) | 2019.09.21 |
백준 2011 - 암호코드 (0) | 2019.09.14 |
백준 4963 - 섬의 개수 (0) | 2019.09.02 |
백준 2667 - 단지번호붙이기 (0) | 2019.08.29 |