문제

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다.

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

풀이

본문의 예제를 그림으로 나타내면 위와 같다. (0,0) 지점을 기준으로 화살표를 계속 따라가다 보면 다음과 같은 사이클을 확인할 수 있다.

일단 사이클이 생성된다면, 사이클 내에 아무 곳에 Safe Zone을 설치한다 해도 최종적으로는 Safe Zone으로 이동할 수 있다.

즉, 문제가 요구하는 것은 결국 해당 지도가 몇 개의 사이클을 가지고 있는가?로 요약될 수 있다.

사이클을 확인하는 방법에는 분리 집합 알고리즘이 있기 때문에, 본 문제를 분리집합으로 풀어보도록 하였다.

우선 for문을 통해 각 셀을 하나씩 살펴본다.

해당 셀과 해당 셀이 가리키는 방향에 있는 셀이 같은 집합에 있는지 살펴보고, 만약 같은 집합에 있지 않다면 같은 집합으로 업데이트하는 방향으로 알고리즘을 전개한다.

코드

# 피리 부는 사나이
import sys
input = sys.stdin.readline

# 입력 받기
num_rows, num_cols = map(int, input().split())
board = [list(input().rstrip()) for _ in range(num_rows)] # 개행문자 제거

# 방향
dirs = {"D" : (1,0), "U"  : (-1,0), "L" : (0,-1), "R" : (0,1)}
parents = list(range(num_cols * num_rows))

# 어떻게 풀 것인가?
# 앞에서부터 하나씩 읽어가면서 union 업데이트
# 총 집합의 개수 찾기

def find_root(cell_id):
    stack = []

    while True:
        stack.append(cell_id)
        parent = parents[cell_id]

        if parent == cell_id:
            break
        else:
            cell_id = parent

    while stack:
        aux_cell = stack.pop()
        parents[aux_cell] = cell_id

    return cell_id
        
def union(root_a, root_b):

    if root_a < root_b:
        parents[root_b] = root_a
    else:
        parents[root_a] = root_b

def get_cell_id (i,j):
    return num_cols * i + j

def get_next_cell(i,j, dir): 
    d_row, d_col = dirs[dir]

    new_i = i + d_row
    new_j = j + d_col

    return new_i, new_j

for i in range(num_rows):
    for j in range(num_cols):

        cell = board[i][j] # 탐색을 진행하는 셀
        new_i, new_j = get_next_cell(i, j, cell) # 셀대로 갔을 때 다음 셀 관련 정보

        cell_id = get_cell_id(i,j)
        next_cell_id = get_cell_id(new_i, new_j)

        # 두 셀이 같은 집합에 속해있는지 파악
        root = find_root(cell_id)
        root_next = find_root(next_cell_id)

        #print(f"cell_id {cell_id}, next_cell_id {next_cell_id}, root {root}, root_next {root_next}")

        # 만약 두 셀이 같은 집합에 포함되지 않았다면
        if root != root_next:
            # 두 셀을 하나의 집합으로 넣는다. (어차피 다음 경로로 갈 것이기 때문)
            union(root, root_next)
            
result_set = set()
parents_set = set(parents)

for i in parents_set:
    root = find_root(i)
    result_set.add(root)

print(len(result_set))

어떤 셀의 root는, 참조될 경우에만 최신 root로 업데이트 된다.
따라서 한 번만 참조되는 셀은 최신 root로 업데이트 되지 않기 때문에, 마지막으로 한 번 더 최신 root로 업데이트 해주는 것으로 최종 cycle의 개수를 찾는다.