1. 문제
설명
농부 존은 최근에 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)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.
출력
베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.
2. 풀이
다른 문제와는 조금 특별한 BFS 문제입니다.
베시가 갈 수 있는 방을 넓혀나가는데 초점을 두고 시뮬레이션을 해봅시다.
세 가지의 2차원 체크 배열 생성
#define MAX 101
int isLight[MAX][MAX]; // 불이 켜진 방인지?
int isCanMove[MAX][MAX]; // 갈 수 있는 방인지?
int visit[MAX][MAX]; // 방문했던 방인지?우리는 베시의 움직임을 그대로 시뮬레이션할 예정입니다.
이 때 베시가 갈 수 있는 방을 체크하기 위해선 위와 같은 세 가지의 상태값이 필요합니다.
차례대로 불이 켜졌는지?, 갈 수 있는지?, 방문했었는지?에 대한 상태입니다.
만약 r행 c열의 방을 갈 수 있는지 체크하려면
- 불이 켜져야하고 ->
isLight[r][c] - 갈 수 있어야하고 ->
isCanMove[r][c] - 방문하지 않았던 방이여야 합니다. ->
!visit[r][c]
우린 이 세 가지 상태값만 가지고 베시의 움직임을 구현할 수 있습니다.
BFS를 진행하면서 다음과 같은 순서대로 탐색을 합니다.
- 현재 있는 방을 기준으로 베시가 갈 수 있는 영역을 넓힙니다.
- 현재 있는 방에서 불을 켤 수 있는 모든 방에 불을 킵니다.
2- 1. 이 때, 불을 켠 방에도 베시가 갈 수 있을 때 그 방의 좌표도 큐에 넣습니다. - 현재 있는 방에서 인접한 방중에 불이 켜진 방의 좌표를 큐에 넣습니다.
이와 같이 행동하면 베시의 움직임을 구현할 수 있습니다.
물론 2번에서 베시가 불을 켠 방이 갈 수 있을 때, 그 방의 좌표를 큐에 넣는 과정 자체가
현실 세상에 대입하면 그 방으로 순간이동? 하는 듯한 느낌이긴 합니다만,
그 방으로 거슬러가기 위해 거꾸로 BFS를 돌리는 미련한 행위보다 시간 절약에 효과적입니다.
3. 전체 코드
#define MAX 101
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M;
int isLight[MAX][MAX]; // 불이 켜진 방인지?
int isCanMove[MAX][MAX]; // 갈 수 있는 방인지?
int visit[MAX][MAX]; // 방문했던 방인지?
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> adjList[MAX][MAX]; // 인접 리스트
queue<pair<int, int>> q;
bool isOut(int y, int x) {
return y < 1 || y > N || x < 1 || x > N;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
while (M--) {
int y, x, b, a;
cin >> y >> x >> b >> a;
adjList[y][x].push_back({ b, a });
}
isLight[1][1] = 1;
isCanMove[1][1] = 1;
visit[1][1] = 1;
q.push({ 1, 1 });
int ans = 1;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
// 현재 있는 방을 기준으로 베시가 갈 수 있는 영역을 넓힙니다.
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
isCanMove[ny][nx] = 1;
}
// 현재 있는 방에서 불을 켤 수 있는 모든 방에 불을 킵니다.
for (pair<int, int> c : adjList[y][x]) {
int ny = c.first;
int nx = c.second;
// 불이 켜져있지 않다면
if (!isLight[ny][nx]) {
isLight[ny][nx] = 1; // 불을 키고
ans++; // 정답 변수 증가
}
// 불을 킨 방이 갈 수 있고, 방문하지 않았을 때
if (isCanMove[ny][nx] && !visit[ny][nx]) {
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
// 현재 있는 방에서 인접한 방중에 불이 켜진 방의 좌표를 큐에 넣습니다.
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (isOut(ny, nx)) continue;
if (isLight[ny][nx] && !visit[ny][nx]) {
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
}
cout << ans;
return 0;
}사실 이 문제는 그림판으로 설명드리는 게 베스트이긴 한데
나중에 그림판 잘 쓰면 꼭 수정해서 포스팅하겠습니다 ㅠㅠ
할 게 너무 많네요... 그래도 잘 이해하셨을 거라 믿습니다.
