Coding 공부

import sys

def input():
    return sys.stdin.readline()

N,M = map(int,input().split())

def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        cnt[X] += cnt[Y]
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}

arr = [list(input()) for _ in range(N)]
make_set = [i for i in range(N*M+1)]
ranks = [1 for _ in range(N*M+1)]
cnt = [1 for _ in range(N*M+1)]
ranks[N*M] = float('inf')

for x in range(N):
    for y in range(M):
        point = x*M+y
        dx,dy = dire[arr[x][y]]
        nx = x + dx
        ny = y + dy

        if 0<=nx<N and 0<=ny<M:
            next_point = (x+dx)*M+y+dy
            union(point,next_point)
        else:
            union(point,N*M)
print(cnt[N*M]-1)

boj.kr/16724 와 동일한 방식으로 풀었다.

그러니깐 미로를 탈출 즉 범위를 벗어나는 경우를 N*M일때로 지정을 해주고, ranks를 최대로 준뒤

무조건 외각이 되었을때 외각이 부모가 되도록 만들어줬다.

주어진 미로의 크기는 N*M인데, N*M + 1 만큼의 make_set과 ranks, cnt를 만들어주고,

미로의 범위 내 이면 두개의 점을 union을 해주고,

범위 밖이면 우리가 만들어놓은 N*M에 union을 해주게 했다.

그리고 마지막에 cnt[N*M]에서 -1을 해주면 전체에서 탈출할 수 있는 칸의 수가 나오게 된다.