이번 문제는 유니온-파인드 알고리즘을 통해 해결하였다. 문제를 보고 사이클 그룹의 갯수를 구해야 한다는 생각을 하고 코드를 작성하였지만, 다른 테스트 케이스들에서 제대로된 그룹의 갯수를 구하지 못하였다. 그래서 다른 사람들의 코드를 참고하게 되었고, 대부분의 사람들이 유니온-파인드 알고리즘을 통해 해결한 것을 알 수 있었다. 아직 유니온-파인드 알고리즘이 익숙하지 않아 코드를 한줄씩 보며 이해하려 노력하였다.

시간이 될 때 유니온-파인드 알고리즘을 자세히 알아보고, 예제도 풀어보는 시간을 가지도록 해야겠다.

Code

n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
mapping = {"U": 0, "D": 1, "L": 2, "R": 3}
visited = [[0 for _ in range(m)] for _ in range(n)]
root = [[(i, j) for j in range(m)] for i in range(n)]
answer = 0
def find(r, c):
    if (r, c) == root[r][c]:
        return (r, c)
    root[r][c] = find(root[r][c][0], root[r][c][1])
    return root[r][c]
def union(nxt, cur):
    nxt_rt = find(nxt[0], nxt[1])
    cur_rt = find(cur[0], cur[1])
    root[cur_rt[0]][cur_rt[1]] = nxt_rt
def dfs(y, x):
    global answer
    visited[y][x] = 1
    d = mapping[grid[y][x]]
    ny, nx = y+dy[d], x+dx[d]
    nxt_rt = find(ny, nx)
    if nxt_rt == (ny, nx) and grid[ny][nx] != 'X':
        union((ny, nx), (y, x))
        dfs(ny, nx)
    else:
        if nxt_rt == (y, x):
            grid[y][x] = 'X'
            answer += 1
            return
        else:
            union((ny, nx), (y, x))
            return
for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            dfs(i, j)
print(answer)