[백준] 불켜기 11967 C++

https://www.acmicpc.net/problem/11967

 

문제해설

해당 문제는 BFS문제이다.

정답은 아니지만 본인은 입력받은 정점을 인접리스트로 관리하고 BFS탐색시 인접리스트의 원소들에 대해서 '불을 먼저 킨다' 그 후에 상하좌우를 살펴 불이 켜져 있으면 이동하는 식으로 로직의 흐름을 짯다.

 

주의할 점은 '불을 켜는 과정에서 무조건 큐에 넣으면 안된다'는 것이다.

혹시 (1, 1) -> (1, 2) -> (1, 3)이후 (1, 3)에서 (2, 1)에 대해 불을 킬 수 있다고 해서 (2, 1)을 바로 넣으면 안된다.

 

본인은 처음에 베시가 불을 킬 수 있는 영역에 대해서 불을 킨다음에 불을 킨 정점을 큐에 추가하였는데, 잘못된 로직이였다. (1, 1) -> (1, 2) -> (1, 3) 순으로 방문하고 (1, 3)에서 (2, 1)에 대해 불을 킬 수 있으니 이 부분을 큐에 넣어 탐색하려고 생각했으나 불을 킬 수 있더라도 방문할 수 없는 경우가 있다.

따라서 불을 킬 수 있다고 해서 바로 큐에 넣어서 탐색할 것이 아니라(불만 킬 수 있는 경우가 있기때문에) 불을 킨 지점의 상하좌우에 대해서 '이미 방문한 정점이 있는지 확인 한 뒤, CC(Conneted Component)라면 큐에 넣어주어야한다.'

정확하게 이동하고 나서 새로운 정점에서 부터 다시 불을 킬 수 있는지 없는지 확인해주어야한다.

 

시간 복잡도

N 은 100이라 최대 O(4NM)이다. 불키는 부분 O(4NM), BFS 탐색하는 부분 O(2 * 4 NM) => O(NM)이라 시간 복잡도는 크게 신경 안써주어도 된다.

 

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;

#define endl "\n"
#define ll long long
#define R first
#define C second
#define F first
#define S second

const int MAX = 104;
const int ON = 1;
const int OFF = 0;
int board[MAX][MAX];
int visit[MAX][MAX];
vector<pair<int, int>> adj[MAX][MAX];
int n, m;
int dc[4] = { -1, 0, 1, 0 }, dr[4] = { 0, 1, 0, -1 };

int main(void)
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	int sc, sr, ec, er;
	for (int i = 1; i <= m; ++i)
	{
		cin >> sc >> sr >> ec >> er;
		adj[sr][sc].push_back({ er, ec });
	}

	queue<pair<int, int>> q;
	board[1][1] = ON;
	visit[1][1] = 1;
	q.push({ 1, 1 });
	int cnt = 1;
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();

		// 불을 먼저 킨다.
		for (auto next : adj[cur.R][cur.C])
		{
			if (board[next.R][next.C] == ON) continue; // 이미 켜져 있다면
			// if (visit[next.R][next.C]) continue; // 방문 했다면
			// 방문 했지만 불을 다른 방향으로 킬 수 있다면? 켜야한다.
			// 
			// 바로 큐에 넣으면 안된다. 불을 킬 수는 있지만 방문할 수 없는 경우가 있을 수 있기때문에 현재 인접한 노드에서 연결되어 있다면 큐에 추가해야한다.
			// q.push({ next.R, next.C });
			board[next.R][next.C] = ON;
			++cnt;

			// 새로 불이 켜진 방이 주변 방문 가능한 방과 연결되어 있는지 확인
			for (int d = 0; d < 4; ++d)
			{
				int nnr = next.R + dr[d];
				int nnc = next.C + dc[d];
				if (nnr < 1 || nnr > n || nnc < 1 || nnc > n) continue;
				if (visit[nnr][nnc]) // 인접한 방문한 노드와 인접하다면 큐에 바로 넣는다.
				{
					q.push({ nnr, nnc });
					visit[nnr][nnc] = 1;
					break;
				}
			}
		}

		// 이동한다.
		for (int d = 0; d < 4; ++d)
		{
			int nr = cur.R + dr[d];
			int nc = cur.C + dc[d];
			if (nr < 1 || nr > n || nc < 1 || nc > n) continue;
			if (board[nr][nc] == OFF || visit[nr][nc]) continue;
			q.push({ nr, nc });
			visit[nr][nc] = 1;
		}
	}

	cout << cnt;
}