[백준 11967] - 불 켜기(C++)[골드2]

📕문제

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

11967번: 불켜기

---

🔎문제설명

bfs 문제에서 조금 변형이 있는 문제입니다.
스위치를 켜면 해당 방으로 이동할 수 있는 것이 아닌, 스위치를 켜고 스위치로 이동가능한지 여부를 판단해야 하는 문제입니다.

다른 bfs문제처럼 바로바로 큐에 넣는 것이 아닌 여부를 판단하고 큐에 넣어야 하기에 헷갈릴 여지가 있다고 생각합니다.

주의할 점은 (1,1)은 원래 불이 켜져있다는 점입니다.

현재 지점에서 켤 수 있는 스위치를 탐색하고, 증가시킵니다.

이제 여기서 스위치를 키고 스위치로 이동 가능한지 체크합니다.

스위치를 중심으로 상하좌우로 탐색해서 한 번이라도 방문한 방이 있다면 스위치가 있는 지역으로 이동할 수 있습니다.

이렇게 스위치에 대한 탐색 -> 스위치로 이동할 수 있는지에 대한 탐색을 합니다.

그다음 현재 지역에서 상하좌우를 탐색해서 스위치가 켜져 있고, 방문하지 않은 지역이 있는지 탐색합니다.

다른 문제와 차별되는 점은 이동할 수 있는 방의 개수를 계산하는 것이 아닌 몇 개의 스위치를 켤 수 있냐입니다.

따라서 방을 이동하고 바로바로 큐에 넣는 것이 아닌 이동할 수 있는 방에 대해서만  큐에 집어넣어야 합니다.

---

💻코드

우선 저는 x, y, a, b에 대해서 튜플을 사용해서 구현했는데, 다른 풀이를 보니 2차원 벡터에 pair 형태로 넣었는데 그 방식이 

훨씬 효율적인 거 같습니다.

#include <iostream>
#include <tuple>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<vector<int>> graph;
vector<vector<int> > v;
vector<tuple<int, int, int, int>> turn;
queue<pair<int,int> >q;
int answer=0;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우
void funct();
int main()
{
    cin >> n >> m;  // n은 n*n 행렬, m은 m개의 입력
    int x, y, a, b; //(x,y)에서 (a,b)를 킬 수 있다.
    graph.assign(n+1,vector<int>(n+1,0));
    v.assign(n+1,vector<int>(n+1,0));
    for (int test = 0; test < m; test++)
    {
        cin >> x >> y >> a >> b;
        turn.emplace_back(x, y, a, b);
    }
    funct();
    cout<<answer<<endl;
}
void funct(){    
    v[1][1]=true; //시작은 (1,1)
    q.push(make_pair(1,1)); 
    graph[1][1]=1;
    answer++;
    while(!q.empty()){
        int row = q.front().first,col = q.front().second;
        q.pop();
        for(auto a: turn){ //여기서 스위치가 이쓴ㄴ 방을 체크해보자.
            if(get<0>(a)==row && get<1>(a)==col){
                int mrow = get<2>(a), mcol = get<3>(a);
                if(graph[mrow][mcol]) //이미 켜진 스위치라면
                    continue;
                answer++; //스위치의 개수를 증가
                graph[mrow][mcol]=1; //스위치 켰다고 표시
                for(int d=0; d<4; d++){ //mrow, mcol은 스위치인 방 스위치 주변에 이미 밟은 곳이 있다면 이동할 수 있음.
                    int trow = mrow+dir[d][0], tcol = mcol+dir[d][1];
                    if(trow < 1 || trow>n || tcol<1 || tcol>n)
                        continue;
                    if(v[trow][tcol]){ //스위치 이동반경 내에 방문한적이 있다면 해당 지역으로 이동가능함
                        q.push(make_pair(mrow,mcol)); //이동할 수 있으므로 큐에 넣음.
                        v[mrow][mcol]=1;
                        break;
                    }
                }
            }
        }
        for(int d=0; d<4; d++){ //현재 위치에서 갈 수 있는 곳을 체크
            int trow = row+dir[d][0], tcol = col+dir[d][1];
            if(trow<1 || trow>n || tcol<1 || tcol>n)
                continue;
            if(!graph[trow][tcol] || v[trow][tcol]) //불이 켜지지 않았거나, 이미 방문했던 방은 방문을 못함
                continue;
            q.push(make_pair(trow,tcol));
            v[trow][tcol]=1;
        }
    }
}