316. 소가 길을 건너간 이유 6

백준

1. Python

import sys
from collections import deque
input = sys.stdin.readline

n, k, r = map(int, input().split())

board = [[[] for _ in range(n + 1)] for _ in range(n + 1)]
cow_map = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
cow_list = []

for _ in range(r):
    r1,c1,r2,c2 = map(int, input().split())
    board[r1][c1].append([r2, c2])
    board[r2][c2].append([r1, c1])

for _ in range(k):
    r, c = map(int, input().split())
    cow_list.append([r,c])
    cow_map[r][c] = 1

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

result = 0
for r, c in cow_list:
    if cow_map[r][c]:
        visited = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
        q = deque()
        q.append([r, c])
        cow_map[r][c] = 0
        cnt = 0
        k -= 1
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 1 <= nx <= n and 1 <= ny <= n and not visited[nx][ny]:
                    if [nx, ny] not in board[x][y]:
                        q.append([nx, ny])
                        visited[nx][ny] = 1
                        if cow_map[nx][ny]:
                            cnt += 1
        result += k - cnt
print(result)