[백준 11967번] 불켜기

문제 링크: https://www.acmicpc.net/problem/11967

11967번: 불켜기

<문제 풀이> BFS

(1, 1)에서 동서남북으로 BFS를 진행하면 되는데,

 

큐에서 꺼낼 때 현재 위치에서 불을 켤 수 있는 모든 방의 불을 켜고, 불이 켜진 방을 현재까지 왔던 경로를 이용해서 들어갈 수 있다면 그 방의 좌표를 큐에 넣으면 됩니다. 

 

현재까지 왔던 경로를 이용해서 불이 켜진 방에 들어갈 수 있는지를 확인하는 방법은 불이 켜진 방의 동서남북을 확인해서 이전에 방문한 적이 있다면 들어갈 수 있는 방이 됩니다.

 

왜냐하면 (1, 1)에서 부터 한 칸씩 이동하기 때문에 (x, y) 정점에 방문 체크가 되어 있다는 건 (x, y)까지 경로가 존재한다는 것입니다.

 

그래서 동서남북 방문체크만 하고 바로 큐에 넣으면 됩니다.

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0 , -1, 0};
 
vector<pair<int, int>> avail[101][101];
bool visited[101][101]; 
bool on[101][101]; 
int cnt = 0;
int n, m;
void bfs() {
    queue<pair<int, int>> Q;
    Q.push({ 1, 1 });
    visited[1][1] = true;
    on[1][1] = true;
    cnt++;
    for (auto room : avail[1][1]) {
        if (!on[room.X][room.Y]) {
            on[room.X][room.Y] = true;
            cnt++;
        }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (auto& room : avail[cur.X][cur.Y]) {
            if (!on[room.X][room.Y]) { //cur의 모든 스위치 누르기
                on[room.X][room.Y] = true;
                cnt++;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = room.X + dx[dir];
                    int ny = room.Y + dy[dir];
                    if (nx < 1 || ny < 1 || nx> n || ny >n)continue;
                    if (visited[nx][ny]) { //불을 켠 방을 이동할 수 있으면
                        Q.push({ room.X, room.Y }); // 다음에 불을 켠 방에서 탐색 시작
                        visited[room.X][room.Y] = true;
                        break;
                    }
                }
            }
        }
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 1 || ny < 1 || nx> n || ny >n)continue;
            if (!on[nx][ny] || visited[nx][ny]) continue;
            Q.push({ nx, ny });
            visited[nx][ny] = true;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        avail[x][y].push_back({ a, b });
    }
    bfs();
    cout << cnt;
 
    return 0;
}