문제 URL : https://www.acmicpc.net/problem/11967
11967번: 불켜기
(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으
www.acmicpc.net
문제 접근법 :
bfs를 이용해야 하는데 어떤곳에서 불을키고난후 다른장소로 이동할수있다고 할대 밟은곳을 또밟아야하는데
여기서 어떻게 또 밟을수있을지 생각해야합니다. m이 2만이라 3차원 배열을 사용하여 visit을 처리하게되면
메모리가 너무크기때문에 사용할수가 없어서 불을킬수 있는곳을 밟게되면
check배열을 새롭게 셋팅하여 어떤곳이든 다시밟을수있또록 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
63
64
65
66
67
68
|
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int>> v[101][101];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, a, b;
cin >> x >> y >> a >> b;
v[x][y].push_back({ a,b });
}
}
bool isrange(int y, int x) {
return 1 <= y && y <= n && 1 <= x && x <= n;
}
int bfs() {
int check[101][101] = { 0 };
int check2[101][101] = { 0 };
int light[101] [101] = { 0 };
light[1][1] = 1;
queue<pair<int, int>> q;
q.push({ 1,1 });
check[1][1] = 1;
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
if (v[y][x].size() && check2[y][x] == 0) {
for (int i = 0; i < v[y][x].size(); i++) {
light[v[y][x][i].first][v[y][x][i].second] = 1;
}
check2[y][x] = 1;
memset(check, 0, sizeof(check));
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && check[ny][nx] == 0 && light[ny][nx] == 1) {
q.push({ ny,nx });
check[ny][nx] = 1;
}
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
res += light[i][j];
}
}
return res;
}
void solve(){
cout << bfs() << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는 점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 3649 로봇 프로젝트 (0) | 2021.12.16 |
|---|---|
| 백준 18808 스티커 붙이기 (0) | 2021.12.15 |
| 백준 3197 백조의 호수 (0) | 2021.12.11 |
| 백준 1726 로봇 (0) | 2021.12.11 |
| 백준 2933 미네랄 (0) | 2021.11.29 |
