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

처음 문제 이해에 애를 먹었지만, 요구사항은 간단했다. 어떤 소들 끼리 길을 안건너고 만날수 있는지 찾으면 되었다.

소들의 위치를 저장해 각 소마다 bfs를 하였다. 소는 최대 10000마리 이므로 10000번 bfs를 돌려주면 되기 때문에, 시간은 넉넉할 것이라 생각했다.

그러면 연결된 길을 어떻게 표시할까를 고민했는데, 배열에 두 쌍을 담을까 생각했지만, 잘 생각해보면 어떤 칸에서 상하좌우로만 갈 수 있기 때문에 각 칸마다 [0,0,0,0]의 상하좌우 배열을 만들고, 연결된 칸을 1로 바꿔주면 쉽게 표현할 수 있었다.

각각의 소가 있는 지점에서 길을 안건너고 만날수 있는 쌍을 모두 찾으면 [a,b][b,a] 와 같이 두가지가 나온다.

소의 개수 전체에서 연결 가능한 전체 쌍은 nP2 이고,
이 전체 쌍에서 찾은 길을 안건너는 연결을 빼주고 2로 나누면 답이된다.

from collections import deque
import math
n,k,r = list(map(int,input().split()))
road = [[[0]*4 for i in range(n+1)] for i in range(n+1)]
cow = []
farm = [[0]*(n+1) for i in range(n+1)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def mark(r,c,a,b):
   for i in range(4):
       if a == dx[i] and b == dy[i]:
           road[r][c][i] = 1

def bfs(x,y):
   queue = deque([])
   queue.append((x,y))
   visited = [[0]*(n+1) for i in range(n+1)]
   visited[x][y] = 1
   cnt = 0
   while queue:
       x,y = queue.popleft()
       visited[x][y] = 1
       for i in range(4):
           nx = x + dx[i]
           ny = y + dy[i]
           if 0 < nx <= n and 0 < ny <= n and not visited[nx][ny] and not road[x][y][i]:
               visited[nx][ny] = 1
               if farm[nx][ny] == 1:
                   cnt += 1
               queue.append((nx,ny))
   return cnt
for i in range(r):
   r1,c1,r2,c2 = list(map(int,input().split()))
   mark(r1,c1,r2-r1,c2-c1)
   mark(r2,c2,r1-r2,c1-c2)

for i in range(k):
   x,y = list(map(int,input().split()))
   farm[x][y] = 1
   cow.append((x,y))

f = math.factorial(k) / math.factorial(k-2)
f = int(f)
cnt = 0
for i in range(len(cow)):
   cnt += bfs(cow[i][0],cow[i][1])

ans = (f-cnt) / 2
ans = int(ans)
print(ans)