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

 

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

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

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:15:24

 

---

 

문제 설명

 

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

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

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

 

입력 및 출력

 

입력

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

 

출력

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

 

입력 예시

3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3

 

출력 예시

2

 

---

 

풀이

 

경로 탐색 문제.

 

1. 각 구획(=목초지)을 나눈다. 사방이 벽(=길)로 가로막힌 구간이 구획의 정의가 된다.
   1. 모든 맵을 탐색하며 방문하지 않은 구획마다 BFS 등의 알고리즘을 통하여 방문 리스트를 매핑하면 된다.
2. 소들의 각 좌표를 토대로, 각 구획에 소가 얼마나 많이 위치하였는지 구한다.
3. 임의의 두 구획을 골랐을 때, 두 구획의 소의 마리 수의 곱은 두 구획의 소를 매칭하는 경우의 수이다. 모든 구획에 대해 이 곱을 구하여 더하면 만날 수 없는 소의 총 쌍 수가 나온다.

 

• road_init : 길(=벽) 초기화 함수. R개의 길의 좌표들을 입력받아 딕셔너리에 저장한다.
• bfs : 너비 우선 탐색 알고리즘. 유효한 좌표이며 아직 방문하지 않은, 또 길에 가로막히지 않고 갈 수 있는 모든 좌표를 탐색한다.
• full_search : 모든 맵에 대해서, 아직 탐색하지 않은 좌표를 만날때마다 bfs를 호출하고 count를 증가시킨다.
• cow_init : 소 좌표 초기화 함수. K개의 소 좌표를 입력받아, 각 구획에 따라 나누어 count한다.
• cal_result : 앞서 3번에서 표현하였던 알고리즘대로 구획에 위치한 소들을 탐색하여 그 결과값인 곱의 합을 출력하다.
• solve : 초기화함수. road_init으로 길을 초기화하고, full_search로 총 구획 좌표인 visited와 구획 개수 idx_cnt를 반환받는다. visited는 cow_init에 전달하여 구획당 소의 마리수를 구하고, idx_cnt는 cal_result함수에 전달하여 구획 탐색에 사용한다.

 

 

 

풀이 코드

from collections import defaultdict, deque
import sys

input = sys.stdin.readline
dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]

N, K, R = map(int, input().split())

cal_actual_coord = lambda x : int(x) - 1
road_count_dict = defaultdict(list)
node_count_dict = defaultdict(int)

def road_init() :
  for _ in range(R) :
    r1, c1, r2, c2 = map(cal_actual_coord, input().split())
    road_count_dict[(r1, c1)].append((r2, c2))
    road_count_dict[(r2, c2)].append((r1, c1))

def bfs(r, c, idx_cnt, visited) :
  q = deque([(r, c)])
  visited[r][c] = idx_cnt

  while q :
    r, c = q.popleft()

    for k in range(4) :
      ar, ac = r + dr[k], c + dc[k]
      if -1 < ar < N and -1 < ac < N and visited[ar][ac] == -1 and (ar, ac) not in road_count_dict[(r, c)] :
        visited[ar][ac] = idx_cnt
        q.append((ar, ac))

def full_search() :
  idx_cnt = 0
  visited = [[-1]*N for _ in range(N)]
  for i in range(N) :
    for j in range(N) :
      if visited[i][j] == -1 :
        bfs(i, j, idx_cnt, visited)
        idx_cnt += 1

  return visited, idx_cnt

def cow_init(visited) :
  for _ in range(K) :
    r, c = map(cal_actual_coord, input().split())
    lands = visited[r][c]
    node_count_dict[lands] += 1

def cal_result(idx_cnt) :
  result = 0
  for i in range(idx_cnt-1) :
    for j in range(i+1, idx_cnt) :
      result += node_count_dict[i] * node_count_dict[j]

  print(result)

def solve() :
  road_init()
  visited, idx_cnt = full_search()
  cow_init(visited)
  cal_result(idx_cnt)

solve()

풀이 완료~