[BOJ] 14466 - 소가 길을 건너간 이유 6 (Python)

 

 

아이디어

 

BFS로 아직 방문하지 않은 소의 위치에서 만날 수 있는 소와 만날 수 없는 남은 소의 수를 곱하여 모두 더한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    N, K, R = map(int, input().split())
    path = dict()
    for _ in range(R):
        r1, c1, r2, c2 = map(int, input().split())
        path[(r1, c1, r2, c2)] = path[(r2, c2, r1, c1)] = 1
    cows = dict()
    for _ in range(K):
        r, c = map(int, input().split())
        cows[(r, c)] = 1
    visited = [[0]*(N+1) for _ in range(N+1)]
    res, total = 0, K
    for r, c in cows.keys():
        if visited[r][c]:
            continue
        visited[r][c] = 1
        stack = [(r, c)]
        cnt = 1
        while stack:
            r, c = stack.pop()
            for dr, dc in delta:
                nr, nc = r+dr, c+dc
                if N >= nr > 0 and N >= nc > 0:
                    if visited[nr][nc] == 0 and path.get((r, c, nr, nc), 0) == 0:
                        visited[nr][nc] = 1
                        stack.append((nr, nc))
                        if cows.get((nr, nc), 0):
                            cnt += 1
        total -= cnt
        res += total*cnt
    print(res)

solution()