[백준] 16724 - 피리 부는 사나이 (G2)

https://www.acmicpc.net/problem/16724

16724번: 피리 부는 사나이

분리집합 + 그래프 탐색 문제이다.

주어진 입력에서 연결요소의 개수를 세면 된다.

 

같은 연결요소인지 아닌지 구분하기 위해 나는 분리집합을 사용했는데,

2차원 분리집합 구현은 처음이라 조금 애를 먹었던 것 같다.

그냥 단순무식하게 튜플을 있는 그대로 비교했는데, 다른 방법도 있을 것 같다.

 

내가 사용한 알고리즘

1. 모든 배열을 순회하면서 아직 방문하지 않은 노드를 만날때마다 해당 노드부터 DFS를 수행한다.

2. DFS를 하면서 만난 모든 노드는 같은 집합으로 묶어준다.

3-1. DFS를 수행하다가 더이상 길이 없으면 answer += 1

3-2. DFS를 수행하다가 맨 처음 시작했던 노드와 같은 집합인 노드로 이동했으면 사이클이니 answer += 1

3-3. DFS를 수행하다가 다른 집합의 방문했던 노드로 이동했으면 이미 세었던 개수에 포함되므로 종료

 

알고리즘은 간단한데, 최근에 BFS 문제를 위주로 풀기도 했고, 2차원 그래프요소에 대해 분리집합을 구현한건 처음이라

구현하는데 애를 먹었다.

(지만 아무리 그래도 G2 난이도는 아닌 것 같다.)

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

TEST_MODE = False
def printMatrix(matrix):
    if not TEST_MODE:
        return
    for i in range(n):
        print(matrix[i])

def DFS(i, j):
    global n, m, answer
    if graph[i][j] == 'D' and i+1 < n:
        if not visit[i+1][j]:
            visit[i + 1][j] = True
            union((i, j), (i+1, j))
            DFS(i+1, j)
        else:
            if find(i, j) == find(i+1, j):
                answer += 1


    elif graph[i][j] == 'U' and i > 0:
        if not visit[i-1][j]:
            visit[i - 1][j] = True
            union((i, j), (i-1, j))
            DFS(i-1, j)
        else:
            if find(i, j) == find(i-1, j):
                answer += 1


    elif graph[i][j] == 'R' and j+1 < m:
        if not visit[i][j+1]:
            visit[i][j + 1] = True
            union((i, j), (i, j+1))
            DFS(i, j+1)
        else:
            if find(i, j) == find(i, j+1):
                answer += 1


    elif graph[i][j] == 'L' and j > 0:
        if not visit[i][j-1]:
            visit[i][j - 1] = True
            union((i, j), (i, j-1))
            DFS(i, j-1)
        else:
            if find(i, j) == find(i, j-1):
                answer += 1

    else: # 이동을 할 수 없을 때
        answer += 1


def find(i, j):
    if parent[i][j] == (i, j):
        return (i, j)

    parent[i][j] = find(parent[i][j][0], parent[i][j][1])
    return parent[i][j]


def union(t1, t2):
    t1 = find(t1[0], t1[1])
    t2 = find(t2[0], t2[1])
    parent[t2[0]][t2[1]] = t1


n, m = map(int, input().split())
visit = [[False for _ in range(m)] for _ in range(n)]
parent = [[(i, j) for j in range(m)] for i in range(n)]
graph = [list(input()) for _ in range(n)]

answer = 0
for i in range(n):
    for j in range(m):
        if not visit[i][j]:

            visit[i][j] = True
            DFS(i, j)


printMatrix(visit)
printMatrix(parent)

print(answer)