[백준 14466번] 파이썬 - 소가 길을 건너간 이유 6

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

조건

• 소가 길을 건너간 이유는 그냥 길이 많아서이다.
• 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.
• 존의 농장에 대대적인 개편이 있었다.
• 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다.
• 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.
• K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다.
• 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

접근 방법

• N x N 행렬을 만들어 준후 길의 위치를 딕셔너리에 담아 준다.
• 길은 양방향이므로 도착지 또한 키값으로도 만들어준다.
• 소의 위치를 cow 배열에 담아 준 후, bfs를 시작
  • 길이 아닌 인접한 곳을 찾으며 소를 만난 경우 no_road 배열에 1로 변경해준후 q에 담아준다.
  • 길은 만나면 continue
• bfs 가 끝난 후 cow 배열을 현재 소의 인덱스 다음부터 시작하여 no_road 배열이 0인 경우 result += 1을 해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import defaultdict, deque  


di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  

def bfs(sti, stj, idx):  
    global result  
    visited = [[0] * N for _ in range(N)]  
    q = deque()  
    q.append((sti, stj))  
    no_road = [[0] * (N) for _ in range(N)]  
    visited[sti][stj] = 1  
    while q:  
        si, sj = q.popleft()  
        for i in range(4):  
            ni, nj = si + di[i], sj + dj[i]  
            if 0<= ni <N and 0<= nj < N and visited[ni][nj] == 0 and not (ni, nj) in road[(si, sj)] :  
                if arr[ni][nj] == 1:  
                    no_road[ni][nj] = 1  

                q.append((ni, nj))  
                visited[ni][nj] = 1  

    for ci, cj in cow[idx+1:]:  
        if not no_road[ci][cj]:  
            result += 1  

N, K, R =map(int, input().split())  

arr = [[0] * N for _ in range(N)]  
road = defaultdict(list)  
cow = []  
result = 0  
for _ in range(R):  
    a, b, c, d = map(int, input().split())  
    road[(a-1, b-1)].append((c-1, d-1))  
    road[(c-1, d-1)].append((a-1, b-1))  
for _ in range(K):  
    a, b = map(int, input().split())  
    arr[a-1][b-1] = 1  
    cow.append((a-1,b-1))  

for i, j in enumerate(cow):  
    bfs(j[0], j[1], i)  

print(result)