[Python/BOJ] 14466. 소가 길을 건너간 이유 6

https://www.acmicpc.net/problem/14466

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

문제

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

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

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

입력

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

출력

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

풀이

Code

import sys
from collections import deque
input = sys.stdin.readline

# 1. bfs 함수 정의
def bfs(caw1, caw2) :
    # 1-1. 방문 여부 리스트 생성
    visited = [[False] * (n+1) for _ in range(n+1)]
    # 1-2. 큐에 첫 번째 소의 위치 삽입
    queue = deque()
    queue.append((caw1[0], caw1[1]))
    # 1-3. 첫 번째 소의 위치 방문 처리
    visited[caw1[0]][caw1[1]] = True
    # 1-4.
    while queue :
        # 큐에서 위치 인덱스 반환
        x, y = queue.popleft()
        for dir_x, dir_y in dirs :
            nx, ny = x + dir_x, y + dir_y
            # 예외 처리
            if nx <= 0 or nx > n or ny <= 0 or ny > n : continue  # 범위를 벗어난 경우
            if (nx, ny) in roads[x][y] : continue   # 길이 있는 경우
            # 다음 위치를 방문하지 않은 경우
            if not visited[nx][ny] :
                # 방문 처리
                visited[nx][ny] = True
                # 큐에 다음 위치 삽입
                queue.append((nx, ny))
    # 1-5. 길을 건너도 되지 않는 경우 0, 길을 건너야 하는 경우 1 반환
    return 0 if visited[caw2[0]][caw2[1]] else 1

n, k, r = map(int, input().split())
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
ans = 0
# 2. 길 정보 입력하기
roads = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(r) :
    x1, y1, x2, y2 = map(int, input().split())
    roads[x1][y1].append((x2, y2))
    roads[x2][y2].append((x1, y1))
# 3. 소 위치 리스트 생성
caws = [list(map(int, input().split())) for _ in range(k)]
# 4.
for i in range(k) :
    for j in range(i+1, k) :
        # 4-1. bfs를 실행해 길을 건너는지 여부 확인
        ans += bfs(caws[i], caws[j])
# 5. 결과 출력
print(ans)