이번 문제는 BFS를 통해 현재 구간에서의 소들의 수를 구하고, 전체에서 이 소들의 수를 빼는 방식으로 구할 수 있었다. 로직도 바로 생각할 수 있었고, 코드도 바로 짤 수 있었지만, 오답이 자꾸 출력되어 시간을 조금 오래 끌었고, 코드를 처음부터 다시 작성하여 이 문제를 해결하였다.

Code

from collections import deque
n, k, r = map(int, input().split())
road = [[[] for _ in range(n+1)] for _ in range(n+1)]
cow_map = [[False for _ in range(n+1)] for _ in range(n+1)]
cow_list = []
for i in range(r):
    r1, c1, r2, c2 = map(int, input().split())
    road[r1][c1].append([r2, c2])
    road[r2][c2].append([r1, c1])
for i in range(k):
    y, x = map(int, input().split())
    cow_list.append([y, x])
    cow_map[y][x] = True
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
result = 0
def find_cow(y, x):
    global k, result
    visited = [[False for _ in range(n + 1)] for _ in range(n + 1)]
    q = deque()
    q.append([y, x])
    cow_map[y][x] = False
    cnt = 0
    k -= 1
    while q:
        cy, cx = q.popleft()
        for d in range(4):
            ny, nx = cy + dy[d], cx + dx[d]
            if 1 <= ny <= n and 1 <= nx <= n and not visited[ny][nx]:
                if [ny, nx] not in road[cy][cx]:
                    q.append([ny, nx])
                    visited[ny][nx] = True
                    if cow_map[ny][nx]:
                        cnt += 1
    result += k - cnt
for y, x in cow_list:
    if cow_map[y][x]:
        find_cow(y, x)
print(result)