백준(BOJ) 14466 소가 길을 건너간 이유 6(Python)

문제 내용.

 

BFS 문제.

길을 건너지 않고 만날 수 있어야 한다는 말은, 길을 건너서는 안 된다는 것으로 해석할 수 있다.

따라서 길로 연결된 두 목초지 사이가 벽으로 막혀있다고 생각하고 문제를 풀 수 있다.

N이 그렇게 크지 않기 때문에, 4차원 리스트를 이용해 두 목초지 사이에 길이 존재하는 지를 저장한다.

그 후에는 전체 농장의 각 구역에 들어 있는 소의 수를 각각 세고, 이들을 각자 서로 곱한 값의 합을 출력하면 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
n,k,r=map(int,input().split())
L=[[[[0]*n for i in range(n)] for j in range(n)] for l in range(n)]
M=[[0]*n for i in range(n)]
visited=[[0]*n for i in range(n)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
count=[]
for i in range(r):
    x1,y1,x2,y2=map(int,input().split())
    L[x1-1][y1-1][x2-1][y2-1]=1
    L[x2-1][y2-1][x1-1][y1-1]=1
for i in range(k):
    x,y=map(int,input().split())
    M[x-1][y-1]=1
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            queue=deque()
            queue.append([i,j])
            visited[i][j]=1
            c=0
            if M[i][j]==1:
                c=1
            while queue:
                x,y=queue.popleft()
                for k in range(4):
                    nx=x+dx[k]
                    ny=y+dy[k]
                    if 0<=nx<n and 0<=ny<n and not visited[nx][ny] and not L[x][y][nx][ny]:
                        visited[nx][ny]=1
                        queue.append([nx,ny])
                        if M[nx][ny]==1:
                            c+=1
            count.append(c)
ans=0
for a,b in combinations(count,2):
    ans+=a*b
print(ans)

BFS 깎는 노인.