[백준 11967] 불켜기

www.acmicpc.net/problem/11967

11967번: 불켜기

문제에 제시된 조건에 대한 이해가 부족했던 문제이다.

 

bfs를 사용하는 것이 맞으나

1. 이미 불이 켜져있는 경우에

2. 그 방에 도달한다면

방에 방문하는 것이 가능하다.

 

문제에서 요구하는 사항은 불이 켜진 방의 수

 

bfs를 여러번 돌리되 fixed point지점을 찾는 것이다. 더 이상 불이 켜진 방의 수가 변하지 않을때까지!!!

처음엔 이게 이해가 안갔다. 하지만 예제를 돌려보면 이해가 가능하다.

 

무조건 (1,1)에서 시작하므로 1라운드에서 불이 켜지는 방은 (1,2) (1,3)이다. 

그리고 상하좌우에 있는 방만 방문가능하다고 했으므로 (1,1)에서 갈 수 있는 방은 (1,2)뿐이다. (2,1)은 아직 불이 안켜져셔 못간다...

 

그렇게 (1,2)가 큐에 푸쉬된다. (1,2)는 켤 수 있는 스위치가 없다. 하지만 이미 불이 켜져있는 (1,3)엔 방문가능하다. 그래서 (1,3)이 다시 푸쉬된다.

 

(1,3)이 켤 수 있는 스위치는 (1,2)와 (2,1)이다. 하지만 주변에 방을 살펴보니 (1,2)는 이미 갔던 곳이고 (2,3)은 불이 안켜져 있어서 방문이 불가능하다. 이제 bfs를 끝내고 다시 (1,1)부터 방문을 시작한다.

 

1라운드에서 켜진 방 수는 (1,1)을 제외하고 3곳이다.((1,2)/ (1,3)/ (2,1) )

2라운드에서 다시 (1,1)로 시작한다 이 때 주의할 점은 방문 표시를 초기화 해야한다는 점이다. 이전 라운드에서 방문했더라도 불이 새로 켜질 수 있는 조건이 될 수 있기 때문

 

그래서 코드는 이렇다

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
int n, m;
int visited[101][101];
int light[101][101];

int x, y, a, b, result = 1;

int drow[4] = {0, 0, -1, 1};
int dcol[4] = {1, -1, 0, 0};

struct R
{
  int x, y;
};

vector<R> v[101][101];
queue<R> q;

bool isValid(int row, int col)
{
  if (row < 1 || col < 1 || row > n || col > n)
  {
    return false;
  }
  return true;
}

int bfs(int row, int col)
{
  int cnt = 0;
  while (!q.empty())
  {
    R fr = q.front();
    q.pop();

    for (int i = 0; i < v[fr.x][fr.y].size(); i++) //그 방에 연결된 스위치로 켜기
    {
      int switch_r = v[fr.x][fr.y][i].x;
      int switch_c = v[fr.x][fr.y][i].y;
      if (light[switch_r][switch_c] == 0)
      {
        light[switch_r][switch_c] = 1;
        cnt++;
      }
    }

    for (int i = 0; i < 4; i++) //방 이동하기
    {
      int near_r = fr.x + drow[i];
      int near_c = fr.y + dcol[i];

	//불이 켜져 있으면 이동한다.
      if (isValid(near_r, near_c) && light[near_r][near_c] == 1 &&
          visited[near_r][near_c] == 0)
      {
        visited[near_r][near_c] = 1;
        q.push({near_r, near_c});
      }
    }
  }

  return cnt;
}
int main(void)
{
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++)
  {
    scanf("%d %d %d %d", &x, &y, &a, &b);
    v[x][y].push_back({a, b});
  }

  while (1)
  {
    memset(visited, 0, sizeof(visited)); //방문 매번 초기화
    q.push({1, 1});
    visited[1][1] = 1;
    light[1][1] = 1;
    int tmp = bfs(1, 1);
    if (tmp == 0) // 더이상 새로운 방이 켜지지 않는다면 종료
      break;
    result += tmp;
  }

  printf("%d\n", result);
  return 0;
}