[BOJ/백준] 17090 미로 탈출하기

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을 해주면 전체에서 탈출할 수 있는 칸의 수가 나오게 된다.