【경쟁 프로 전형적인 90문】012의 해설(python)

개요

경쟁 프로 전형 90문 의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.

이슈012-Score Sum Queries

문제 개요

흰색으로 칠한 H × W의 매스 눈에 대해 다음 두 패턴 중 하나의 Q 개의 쿼리를 처리합니다.
1. 흰 매스(r, c)를 빨간색으로 바른다
2. (r1, c1), (r2, c2)의 2점이 주어졌을 때, 다음의 조건을 모두 만족하고 있는지 판정한다.
- 두 점이 모두 빨간색으로 칠해져 있습니다.
- 2점이 붉은 매스를 따라가면 연결되어 있다

해결 방법

이 문제는 Union-Find를 알거나 모르는 문제입니다.
일단 간단히 설명하면 Union-Find는 그룹화 관리를 매우 빠르게 구현할 수 있는 데이터 구조로,
어느 집합의 그룹 나누기나, 같은 그룹에 속하고 있는지 등을 고속으로 판정할 수 있습니다.
Union-Find에 대한 자세한 내용은 다음 슬라이드 등을 참조하십시오.


인용 원본: Union find(소집합 데이터 구조) from Atcoder Inc.

Union-Find를 사용하면 각 쿼리의 처리는 다음과 같이 생각할 수 있습니다.
1. 흰 매스(r, c)를 빨간색으로 바른다
→ 흰색 송어를 빨간색으로 바르고 인접한 송어에 빨간색 송어가 있으면 연결합니다.

2. (r1, c1), (r2, c2)의 2점이 주어졌을 때, 붉은 매스를 따라가면, 2점이 연결되어 있다
→ 같은 그룹에 속하는지 결정

여기까지, 순서를 알았으므로, 이하에서 실제로 구현해 가고 싶습니다.



인용 소스 : 경쟁 프로 전형 90문 Github

구현

answer.py

# 入力の受け取り
H, W = map(int, input().split())
Q = int(input())

# 二次元配列を一次元化する関数
def flatten(h, w):
  return h+(H+1)*w

# 赤塗りかどうかを判定する配列。配列の要素数をnに格納。
M = [False]*((H+1)*W)
n = len(M)

# UnionFindの実装例
class UnionFind():
  def __init__(self, n):
      self.n = n
      self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x


  def same(self, x, y):
    return self.find(x) == self.find(y)

# 要素数nを入れて、Union Findのインスタンスを作成。
uf = UnionFind(n)


for _ in range(Q):
  q = list(map(int, input().split()))

# ti = 1の時、[r, c]を赤く塗り、隣接マスを探索、もし赤なら、グループを結合する。
  if q[0] == 1:
    r, c = q[1]-1, q[2]-1
    x = flatten(r, c)
    M[x] = True
    for i, j in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
      r_dash, c_dash = r+i, c+j
      y = flatten(r_dash, c_dash)
      if 0 <= r_dash < H and 0 <= c_dash < W:
        if M[y]:
          uf.union(x, y)
# ti = 2の時、[r1, c1], [r2, c2]が共に赤なら、同じグループに属するか判定。
  else:
    x = flatten(q[1]-1, q[2]-1)
    y = flatten(q[3]-1, q[4]-1)
    if M[x] and M[y] and uf.same(x, y):
      print("Yes")
    else:
      print("No")

마지막으로

문제의 해설을 읽어도 다른 사람의 코드를 봐도 확실히 모르는 분
힘에 조금이라도 될 수 있으면 다행입니다.
코드의 개선점이나 그 외, 의견, 질문등 있으면, 부담없이 코멘트해 주세요.

여기까지 읽어 주셔서 감사합니다.