[백준 16724번] 파이썬 - 피리 부는 사나이

백준 16724_피리 부는 사나이

시간 제한 1초, 메모리 제한 256MB

# 조건

• 피리 부는 사나이 성우는 오늘도 피리를 분다.
• 성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다.
  • 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.
• 이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다.
• 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다.
• 성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

• 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.
• 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.
• 지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

• 첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다

# 접근 방법

• 사이클이 존재하는 곳 마다 1개씩 놔주면 된다.
• 모든 지점에서 확인해야 하므로 서로소 집합, 즉 분리 집합을 이용해준다.
  • 부모 배열의 좌표를 0,0 을 0부터 시작하여 N*M까지의 정수로 기록해준다.
• UNION에 넣어줄 때는, 해당 좌표의 수 = i * M + j와 같다.
  • 즉 2행 0열의 경우 8 이므로 2 * 4 + 0 과 같다.
• set을 활용하여 나오는 길이가 최소 SAFE ZONE의 개수이지만 그 전에,
• parent 리스트를 다시 find 함수를 이용하여 부모 노드를 한번 더 갱신해주어야 한다.
  • 좌표가 순서대로 진행되기 때문에!!
• dfs를 이용하여도 풀 수 있다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  


def find(x):  
    if parent[x] != x:  
        parent[x] = find(parent[x])  
    return parent[x]  

def union(a, b):  
    a = find(a)  
    b = find(b)  
    if a<b:  
        parent[b] = a  
    else:  
        parent[a] = b  

N, M = map(int, input().split())  
arr = [list(input().strip()) for _ in range(N)]  
parent = [i for i in range(N*M)]  

num= 0  


for k in range(N):  
    for l in range(M):  
        if arr[k][l] == 'D':  
            union(k*M+l, (k+1)*M+l)  
        elif arr[k][l] == 'L':  
            union(k*M+l, k*M+l-1)  
        elif arr[k][l] == 'R':  
            union(k*M+l, k*M+l+1)  
        else:  
            union(k*M+l, (k-1)*M+l)  

print(len(set(map(lambda x: find(x), parent))))