출처:https://www.acmicpc.net/problem/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)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.
풀이
이 문제도, 단순하게 풀면 틀리기 쉬운 문제이다. 문제를 천천히 정독하고 문제의 상황을 머릿속으로 그려내는게 왜 중요한지 깨닫게 해주는 문제이다.
베시를 BFS로 탐색 했을 때, 이미 방문했던 점을 다시 재방문하는 것은 무한루프를 돌 수 있기 때문에, 방문배열을 쓰게될텐데 아래와 같은 예외상황이 발생할 수 있다.
배시가 운좋게도 이미 방문했던 지점에서 모두 다 켜봤는데 더 이상 킬 곳이 없을 수 있지만, 이미 지나온 방을 통해서 다시 불켜진 방을 들어가게 될 수도 있다.
그렇다면, 어떻게 이걸 해결할 수 있을 지 생각을 해보자.
- 갈 수 있는 곳을 다 가보고 방문배열을 초기화 해준다.
- 꽤 직관적인 방법이다. 시간복잡도가 되는지 생각을 해봐야한다. 갈 수 있는 곳을 다 가본다는 의미는 최악의 경우에는 O(N^2)일거다. 하지만, 이 경우에는 새롭게 켜질 지점이 없다 .위 문제의 최악의 경우는 한쪽으로 쭉 갔다가 다시 원점으로 돌아가는 경우이다. O(N^3)이 최악의 케이스이다.
(1,1)에서 (1,2)킴 -> (1,2)에서 (1,3)킴 ->(1,3)에서 (2,1)킴.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct Point
{
int x;
int y;
};
int N, M;
vector<Point> v[101][101];
bool light[101][101];
bool visited[101][101];
bool outOfRange(int x, int y)
{
return (x < 0 || x > N || y < 0 || y > N);
}
void bfs()
{
// 불이 켜졌다면, 왔던 길도 다시 와바야한다.
while (1)
{
memset(visited, false, sizeof(visited));
queue<Point> Q;
visited[1][1] = true;
light[1][1] = true;
Q.push({1, 1});
bool IsNewLight = false;
while (!Q.empty())
{
Point cur = Q.front();
Q.pop();
// 불 키기
if (!v[cur.x][cur.y].empty())
{
for (int i = 0; i < v[cur.x][cur.y].size(); i++)
{
int target_x = v[cur.x][cur.y][i].x;
int target_y = v[cur.x][cur.y][i].y;
light[target_x][target_y] = true;
}
v[cur.x][cur.y].clear();
IsNewLight = true;
}
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (outOfRange(nx, ny))
continue;
// 이미 방문을 했다면 갈 필요가 없고 , 불이 꺼져있으면 못간다
if (visited[nx][ny] || !light[nx][ny])
continue;
visited[nx][ny] = true;
Q.push({nx, ny});
}
}
// 만약, 새로 켜진 불이 없다면, 다시 가볼 필요가 없다.
if (!IsNewLight)
{
break;
}
}
}
int chk_ans()
{
int cnt = 0;
for (int i = 0; i <= N; i++)
{
for (int j = 0; j <= N; j++)
{
if (light[i][j])
cnt++;
}
}
return cnt;
}
int main()
{
cin >> N >> M;
int ans = 0;
int x, y, a, b;
for (int i = 0; i < M; i++)
{
cin >> x >> y >> a >> b;
v[x][y].push_back({a, b});
}
bfs();
ans = chk_ans();
cout << ans << '\n';
return 0;
}- 배열방문의 의미를 부여해준다.
- True/False를 방문배열로 쓰거나, 거리를 방문배열로 쓰는게 아니라, int visited[x][y]로 지정해놓고, visited[x][y] =1은 어떤 상태, 2는 어떤 상태, 3은 어떤 상태 ...n은 어떤 상태 등으로 숫자 1개당 1개의 상태를 나타내는 방법도 있다.
예를들어, 위같은 경우, 내가 갈 수는 있었지만, 불이 꺼진 곳이 나중에 문제가 되된다. 아래와 같이 방문배열의 숫자에 의미를 담을 수 있다.
visited[x][y] = 0 : 방문을 한번도 안함
visited[x][y] = 1 : 불이 켜진 상태
visited[x][y] = 2 : 새롭게 불을 킨 상태
visited[x][y] = 3 : 내가 갈 수는 있지만, 불이 꺼져있어서 나중에 켜질 수도 있는 상태
#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#define X first
#define Y second
using namespace std;
int n, m, count = 1;
vector<pair<int, int>> lights[101][101];
int visited[101][101];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
queue<pair<int, int>> q;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
while (m--) {
int x, y, a, b;
cin >> x >> y >> a >> b;
lights[x][y].push_back({a, b});
}
state[1][1] = 1;
q.push({1, 1});
while (!q.empty()) {
int x = q.front().X;
int y = q.front().Y;
q.pop();
for (auto light : lights[x][y]) {
int a = light.X;
int b = light.Y;
if (!visited[a][b]) {
visited[a][b] = 2;
count++;
continue;
}
if (visited[a][b] == 3) {
visited[a][b] = 1;
count++;
q.push({a, b});
}
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || ny < 1 || nx > n || ny > n)
continue;
if (!visited[nx][ny])
visited[nx][ny] = 3;
else if (visited[nx][ny] == 2) {
visited[nx][ny] = 1;
q.push({nx, ny});
}
}
}
cout << count;
}