[BOJ] #11967 불 켜기

[BOJ] #11967 불 켜기

 

 

문제

농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

 

 

---

FLOW

출발점 방인 (1,1)에서 시작하며, 차례대로 방문하며 불을 켠다.

불을 켜고, 그 방으로 이동 가능한지 check해야한다. (갈 수 없다면 queue에서 순회를 할 필요가 없다)

모든 경로를 매번 가지고 있어야 하는 문제였다. 만약, A에서 C의 불을 밝힐 수 있었지만, C에 방문을 하지 못하는 경우가 있을 수 있다. 하지만, 이후 A와 C사이의 방인 B의 불이 켜졌다면, C를 방문해서 C에서 불을 밝힐 수 있다.

이 점을 고려하지 못하여 꽤나 오래 삽질했다.

 

 

  #include <cstring>
  #include <iostream>
  #include <queue>
  #include <vector>
  using namespace std;
  const int MAX = 101;
  bool light[MAX][MAX];
  bool visited[MAX][MAX];
  bool temp[MAX][MAX]; // 불이 켜졌지만 방문 못 했던 방들을 고려한다.
  vector<pair<int, int>> v[MAX][MAX];
  queue<pair<int, int>> q;
  int n, m;
  int dirX[4] = {0, 1, 0, -1};
  int dirY[4] = {-1, 0, 1, 0};

  void bfs() {
    light[1][1] = true;
    visited[1][1] = true;
    q.push(make_pair(1, 1));

    while (!q.empty()) {
      int curX = q.front().first;
      int curY = q.front().second;
      q.pop();

      if (!v[curX][curY].empty()) {
        for (int i = 0; i < v[curX][curY].size(); i++) {
          int nextX = v[curX][curY][i].first;
          int nextY = v[curX][curY][i].second;
          light[nextX][nextY] = true;
          if (temp[nextX][nextY] && !visited[nextX][nextY]) {
            q.push(make_pair(nextX, nextY));
            visited[nextX][nextY] = true;
          }
        }
        v[curX][curY].clear();
      }

      for (int i = 0; i < 4; i++) {
        int nextX = curX + dirX[i];
        int nextY = curY + dirY[i];

        if (nextX < 1 || nextX > n || nextY < 1 || nextY > n) {
          continue;
        }
        if (visited[nextX][nextY]) {
          continue;
        }
        if (!light[nextX][nextY]) {
          temp[nextX][nextY] = true;
        } else if (light[nextX][nextY]) {
          q.push(make_pair(nextX, nextY));
          visited[nextX][nextY] = true;
        }
      }
    }
  }

  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    bfs();

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (light[i][j] == true) {
          cnt++;
        }
      }
    }
    cout << cnt;
    return 0;
  }