[BAE/<JOON> 문제풀이] 11967. 불켜기

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

 

서론

틀렸습니다. 게시판 반례 전부 동작 확인 후 큰일남을 느낌. 이 후 맞왜틀의 반복. 기적의 반례 발견. 성공..

---

풀이

불을 켠 방 수를 세야 한다. 방문한 방 수가 아니라. 문제를 잘 읽지 않으면 여기서 틀린다.

사실 탐색 자체는 매우 간단하다. bfs 하면서 불켜고 불 켠 주변방에 이미 탐색된 방이 있다면 그 방만 다시 탐색하면 된다.

아래와 같은 반례를 회피하기 위해 이러한 로직이 필요하다.

 

위 그림의 화살표 진행 방향으로 이동했을 때 r1에 도착해서 r2의 불을 켠다면 r2로 가는 경로는 이미 탐색되었으므로 r2에서 켤 수 있는 방은 켜지 못하게되는 불상사가 발생한다. 따라서 어떤 방의 불을 켰다면 그 방의 상하좌우 방을 재탐색하고 이미 방문한 경로가 있을 경우 다시 탐색해줘야 한다.

 

나는 1번 방에 있는 모든 스위치를 켜고 그 수를 sum값에 더 한뒤 탐색을 시작했는데, 1번 방에 같은 방 번호의 스위치가 주어지는 경우를 고려하지 않았다.. 그게 최종 반례였다. 맞왜틀 2시간했는데 너무 허무하다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <list>
using namespace std;
using ll = long long;
struct pa {
	ll sum, cnt;
};
struct pos {
	int x, y;
};
int mvx[4] = { 0 ,1, 0, -1 };
int mvy[4] = { 1, 0, -1, 0 };
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m; vector<vector<vector<pos>>> arr(n + 1, vector<vector<pos>>(n + 1)); vector<vector<int>> ch(n + 1, vector<int>(n + 1)), vis(n + 1, vector<int>(n + 1));
	for (int i = 1; i <= m; i++) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		arr[x1][y1].push_back({ x2, y2 });
	}
	ch[1][1] = 1; vis[1][1] = 1;
	int sum = 1;
	for (auto p : arr[1][1]) {
		sum += 1 - ch[p.x][p.y];
		ch[p.x][p.y] = 1; 
	}
	queue<pos> q; q.push({ 1, 1 });
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int mx = cur.x + mvx[i];
			int my = cur.y + mvy[i];
			if (mx > n || my > n || mx < 1 || my < 1 || vis[mx][my] == 1 || ch[mx][my] == 0) continue;
			vis[mx][my] = 1;
			for (auto p : arr[mx][my]) {
				sum += 1 - ch[p.x][p.y];
				ch[p.x][p.y] = 1;
				for (int j = 0; j < 4; j++) {
					int nx = p.x + mvx[j];
					int ny = p.y + mvy[j];
					if (nx > n || ny > n || nx < 1 || ny < 1 || vis[nx][ny] == 0) continue;
					q.push({ nx, ny });
				}
			}
			q.push({ mx, my });
		}
	}
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << vis[i][j] << " ";
		}
		cout << "\n";
	}*/
	cout << sum;
	return 0;
}