https://www.acmicpc.net/problem/14466
14466번: 소가 길을 건너간 이유 6첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.www.acmicpc.net
처음엔 단순히 모든 소에 대해 bfs를 실행하여, 만나지못하는 모든 소를 구하고,
만난소+1(자신) 에다가 만나지못한 모든소를 곱해준다음, 쌍이니 2로 나눠주는식으로 구했다.
이렇게 통과를 하긴 했는데, 다른사람들정답을 보니 전부나보다 빨랐다. (1048ms나옴)
약속이 있어서 나갔다가 생각났는데,
arr에 대하여 bfs로 구역을 나누고, 배열에 구역별 소의 수를 집어넣는다.
그 후 현재 구역이 만나지 못하는 소의 수는 (총소의수 - 현재구역의 소의 수)*현재구역의 소의 수이다.
그 후 다음구역으로 넘어갈 때는, 중복을 방지하기 위하여 총 소의수-=현재구역의 소의 수 를 해주고 넘어간다.
이렇게 하면 배열전체를 한번만 탐색해도 되므로, 10배정도 빠르다. (128ms)
import sysfrom collections import dequeinput=sys.stdin.readlineroad=set()
move=[[-1,0],[1,0],[0,-1],[0,1]]cow=set()n,k,r=map(int,input().split())answer=0
arr=[[0 for _ in range(n)]for _ in range(n)]for _ in range(r):
a,b,c,d=map(lambda x: int(x)-1,input().split()) road.add((a,b,c,d))
road.add((c,d,a,b))for _ in range(k):
a,b=map(lambda x: int(x)-1,input().split()) cow.add((a,b))def bfs(i,j):
res=[0,1][(i,j) in cow] arr[i][j]=1 q=deque([(i,j )])
while q: cx,cy=q.popleft() for a,b in move:
nx,ny=cx+a,cy+b
if 0<=nx<n and 0<=ny<n and (cx,cy,nx,ny) not in road and arr[nx][ny]==0:
arr[nx][ny]=1 q.append((nx,ny))
if (nx,ny) in cow: res+=1 return res
sec=[]for i in range(n): for j in range(n):
if arr[i][j]==0: sec.append(bfs(i,j))# print(sec)# exit()
for i in range(len(sec)-1): tmp=sec[i] k-=tmp answer += k*tmp
print(answer)재밌는문제였다.