[BOJ/백준][Gold4] 11967 : 불켜기 (C++)

https://www.acmicpc.net/problem/11967

11967번: 불켜기

 

 

 

[난이도] Gold4
[유형] BFS

[풀이]
visit배열의 값을 3가지로 사용한다. (0:불도 안켜진 상태 1:불만 켜진상태 2:방문완료한 상태)
(1,1)부터 BFS를 시작한다. 인접하고 불이 켜진 곳을 queue에 넣기 전에
현재 위치에서 킬 수 있는 불을 켜준다.
여기서 주의할 점이 방금 불을 켠 점의 인접한 곳에 (2:방문 완료한 상태)인 점이 있다면 이곳도
방문할 수 있는 점에 추가되어야 하기 때문에 queue에 넣어줘야 한다.

 

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,cnt,visit[102][102],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1}; 
vector<pair<int,int>> adj[101][101];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int y,x,b,a;
        scanf("%d%d%d%d",&x,&y,&a,&b);
        adj[y][x].push_back({b,a});
    }
    queue<pair<int,int>> q;
    q.push({1,1});
    visit[1][1]=2;
    int cnt=1;
    while(!q.empty()){
        int qsz=q.size();
        auto f = q.front(); q.pop();
        int y = f.first, x=f.second;
        for(auto p : adj[y][x]){
            int ny = p.first, nx = p.second;
            if(!visit[ny][nx]){
                for(int i=0;i<4;i++){
                    int ty=ny+dy[i],tx=nx+dx[i];
                    if(visit[ty][tx]==2) {
                        q.push({ty,tx});
                        break;
                    }
                }
                visit[ny][nx]=1;
                cnt++;
            }
        }
        for(int i=0;i<4;i++){
            int ny = y+dy[i], nx= x+dx[i];
            if(visit[ny][nx]==1){
                visit[ny][nx]=2;
                q.push({ny,nx});
            }
        }
    }
    printf("%d",cnt);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11967.cpp