다른 소를 만날때마다 count를 1씩 증가시키고, 한 소의 bfs가 다 끝나면 n - count를 ans에 저장
ans / 2를 출력
코드
#include <iostream>#include <list>#include <cstring>#include <vector>using namespace std;int n, k, r, map[101][101];list<pair<int, int>> l;bool visit[101][101], path[101][101][4];pair<int, int> cow[101];int bfs();int main() { cin >> n >> k >> r; int a, b, c, d, e, f, g; for (int i = 0; i < r; i++) { cin >> a >> b >> c >> d; e = a - c, f = b - d; if (e == 1) g = 0; else if (e == -1) g = 2; else if (f == 1) g = 3; else g = 1; path[c][d][g >= 2 ? g - 2 : g + 2] = true; path[a][b][g] = true; } for (int i = 1; i <= k; i++) { cin >> cow[i].first >> cow[i].second; map[cow[i].first][cow[i].second] = i; } cout << bfs();}int bfs() { int ans = 0, offset[4][2] = { {-1,0}, {0, 1}, {1, 0}, {0, -1} }; for (int i = 1; i <= k; i++) { int count = 0; visit[cow[i].first][cow[i].second] = true; l.push_back({ cow[i].first, cow[i].second }); while (!l.empty()) { int r = l.front().first, c = l.front().second; l.pop_front(); if (map[r][c] != 0) count++; for (int i = 0; i < 4; i++) { int nr = r + offset[i][0], nc = c + offset[i][1]; if (nr <= n && nr >= 1 && nc <= n && nc >= 1 && !visit[nr][nc] && !path[r][c][i]) { l.push_back({ nr, nc }); visit[nr][nc] = true; } } } ans += k - count; memset(visit, 0, sizeof(visit)); } return ans / 2;}