[백준/C++] 11967번 불켜기
2021. 4. 4. 17:14ㆍ알고리즘/BFS DFS
728x90
반응형
문제: www.acmicpc.net/problem/11967
문제풀이
불을 켤 때마다 bfs를 다시 해주어야 불을 켤 수 있는 좌표를 모두 찾을 수 있다.
코드
#include <iostream>
#include <queue>
using namespace std;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int board[101][101];
int visited[101][101];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<pair<pair<int,int>,pair<int,int>>> v;
while(m--){
int x,y,a,b;
cin>>x>>y>>a>>b;
v.push_back({{x,y},{a,b}}); //스위치
}
int temp = 0;
queue<pair<int,int>> q;
while(true){
for(int i=0; i<=n; i++)
fill(visited[i], visited[i]+n+1, 0);
q.push({1,1});
visited[1][1] = 1;
board[1][1] = 1;
while(!q.empty()){
pair<int,int> cur = q.front();
q.pop();
for(int i=0; i<v.size(); i++){
if(cur == v[i].first)
board[v[i].second.first][v[i].second.second] = 1;
}
for(int dir=0; dir<4; dir++){
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if(nx<1||nx>n||ny<1||ny>n) continue;
if(visited[nx][ny] || !board[nx][ny]) continue;
visited[nx][ny] = 1;
q.push({nx,ny});
}
}
int cnt=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(board[i][j] == 1)
cnt++;
if(temp != cnt) //불이 켜진 곳의 개수가 이전 bfs때와 같으면 더 켤 수 있는 방이 없음
temp = cnt;
else
break;
}
cout<<temp;
return 0;
}
결과
728x90
반응형
'알고리즘 > BFS DFS' 카테고리의 다른 글
[백준/C++] 13913번 숨바꼭질 4 (0) | 2021.04.03 |
---|---|
[백준/C++] 1600번 말이 되고픈 원숭이 (0) | 2021.04.03 |
[백준/C++] 6593번 상범 빌딩 (0) | 2021.04.02 |
[백준/C++] 13549번 숨바꼭질 3 (0) | 2021.04.02 |
[백준/C++] 5014번 스타트링크 (0) | 2021.04.01 |