[C++/백준] 11967번: 불켜기

문제 링크

11967번: 불켜기

 

풀이

BFS 문제

1. 먼저 각 위치에서 스위치를 통해 켤 수 있는 위치는 인접 리스트와 같이 구현하였다.
2. 방문한 자리를 표시하기 위한 visited와 불이 켜져있는 것을 표시하기 위한 room을 만들었다.
3. 여느 BFS와 같이 queue를 이용해 구현한다.
   1. 현재 위치인 tx, ty에서 연결되어 있는 자리가 불이 꺼져있으면 불을 켜주면서 answer++해주고, 해당 위치가 방문했던 위치라면 queue에 push해준다.
   2. 상하좌우 진출하면서, 범위를 벗어나거나 방문했던 곳이라면 continue, 불만 꺼져있으면 visited 처리해준 뒤에, queue에 넣지는 않는다.(진출하지는 않음) 1번에서 불이 켜진다면 진출할 것이다.
4. answer를 return한 뒤 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

int BFS(vector<vector<vector<pair<int, int>>>> &swit)
{
    vector<vector<int>> visited(n + 1, vector<int>(n + 1));
    vector<vector<int>> room(n + 1, vector<int>(n + 1));
    queue<pair<int, int>> q;
    visited[1][1] = 1;
    room[1][1] = 1;
    q.push({ 1,1 });

    int answer = 1;

    while (!q.empty())
    {
        int tx = q.front().first;
        int ty = q.front().second;
        q.pop();
        for (int i = 0; i < swit[tx][ty].size(); i++)
        {
            int onX = swit[tx][ty][i].first;
            int onY = swit[tx][ty][i].second;
            if (room[onX][onY] == 0)
            {
                room[onX][onY] = 1;
                answer++;
                if (visited[onX][onY]) q.push({ onX,onY });
            }
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = tx + dx[i];
            int ny = ty + dy[i];
            if (ny < 1 || ny >= n + 1 || nx < 1 || nx >= n + 1) continue;
            if (visited[nx][ny]) continue;
            visited[nx][ny] = 1;
            if (room[nx][ny] == 0) continue;
            q.push({ nx,ny });
        }
    }

    return answer;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int m;
    cin >> n >> m;

    vector<vector<vector<pair<int, int>>>> swit(n+1, vector<vector<pair<int,int>>>(n+1));
    for (int i = 0; i < m; i++)
    {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        swit[x][y].push_back({a,b});
    }

    cout << BFS(swit);

}