피리 부는 사나이

• 그래프로 생각하면, 모든 노드는 outdegree가 1이라서, 어디서 출발하든지 결국은 어떤 사이클에서 끝나게 되어있다. 사이클마다 safe존을 하나씩 설치하면 끝이다. 결국 safe존의 최소 갯수 = 커넥티드 컴포넌트의 수 = 사이클의 갯수이다.
• 커넥티드 컴포넌트의 갯수는 DFS를 이용해서 구해도 되고, Disjoint Set을 이용해서 구해도 상관 없다. 여기에서는 Disjoint Set을 이용해서 구현.

"""Solution code for "BOJ 16724. 피리 부는 사나이".

- Problem link: https://www.acmicpc.net/problem/16724
- Solution link: http://www.teferi.net/ps/problems/boj/16724

Tags: [Disjoint Set]
"""

import itertools
import sys
from teflib import disjointset


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    grid = [sys.stdin.readline().rstrip() for _ in range(N)]

    delta = {'U': -M, 'D': M, 'L': -1, 'R': 1}
    group_count = N * M
    dsu = disjointset.DisjointSet(group_count)
    counter = itertools.count()
    for row in grid:
        for direction in row:
            cur_cell = next(counter)
            adj_cell = cur_cell + delta[direction]
            try:
                dsu.union(cur_cell, adj_cell, should_raise=True)
            except ValueError:
                pass
            else:
                group_count -= 1

    print(group_count)


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet