문제

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

# 14466
import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

# 1. 길을 건너야 하는 경우엔 이동하지 않는다.
# 2. 각각의 소가 다른 소와 만날 수 있는지 구한다.

n, k, r = map(int, input().split())
graph = []
for i in range(n+1):
    graph.append([])
    for _ in range(n+1):
        graph[i].append([])
        
for _ in range(r):
    r1, c1, r2, c2 = map(int, input().split())
    graph[r1][c1].append((r2, c2))
    graph[r2][c2].append((r1, c1))
    
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
    
    
def bfs(x, y):
    global n, graph
    arr = [[-1] * (n+1) for _ in range(n+1)]
    arr[x][y] = 0
    
    queue = deque()
    queue.append((x, y))
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 1 or ny < 1 or nx > n or ny > n:
                continue
            
            if (nx, ny) in set(graph[x][y]):
                continue
                
            if arr[nx][ny] == -1 or arr[x][y] + 1 < arr[nx][ny]:
                arr[nx][ny] = arr[x][y] + 1
                queue.append((nx, ny))
                
    return arr


cows = [list(map(int, input().split())) for _ in range(k)]
cnt = 0
for i in range(k):
    x, y = cows[i][0], cows[i][1]
    arr = bfs(x, y)
    
    for j in range(i+1, k):
        x, y = cows[j][0], cows[j][1]
        if arr[x][y] == -1:
            cnt += 1
            
print(cnt)

백준 14466 소가 길을 건너간 이유 6