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

14466번: 소가 길을 건너간 이유 6

문제

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

출력

길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.

코드

from collections import deque

n, k, r = map(int, input().split())
# 길 정보
road = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(r):
    r1, c1, r2, c2 = map(int, input().split())
    road[r1][c1].append([r2, c2])
    road[r2][c2].append([r1, c1])
    
# 소의 위치
cow_position = []
for _ in range(k):
    cow_position.append(list(map(int, input().split())))

# BFS
def bfs(x, y):
    q = deque([(x,y)])
    visited[x][y] = True
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 소가 길을 건너지 않고 갈 수 있는 모든 곳을 탐색
    while q:
        row, col = q.popleft()
        for i in range(4):
            nr = row + dx[i]
            nc = col + dy[i]
            # 범위를 벗어나면 안됨
            if nr < 1 or nr > n or nc < 1 or nc > n:
                continue
            # 이미 방문한 곳일 때
            if visited[nr][nc]:
                continue
            # 길을 건너야하는 경우
            if [nr, nc] in road[row][col]:
                continue
            q.append((nr, nc))
            visited[nr][nc] = True

ans = 0
for idx in range(len(cow_position)):
    visited = [[False for _ in range(n+1)] for _ in range(n+1)]
    # 소가 방문하지 못한 목초지는 visited에 False로 표시
    bfs(cow_position[idx][0], cow_position[idx][1])
    # 현재 탐색한 소 이후의 소들 중 방문하지 않은 목초지에 있는 소가 있으면 ans += 1
    for r,c in cow_position[idx+1:]:
        if not visited[r][c]:
            ans += 1
print(ans)