BOJ 16724 파이썬

피리 부는 사나이

접근

문제를 그림으로 표현해줘서 문제를 이해하는데 도움이 많이 되었다. 결론적으로는 몇 개의 집합이 있는지 찾는 문제였다. a위치에서 b위치로 갈 수 있다면 같은 집합인 것이다.

1. a위치에서 b위치로 갈 수 있다면 같은 집합이다.
2. 방문하지 않은 위치에 대하여 DFS을 실행하여 집합을 찾는다.
   • 다음 위치가 현재 위치와 같은 집합이 아니라면 방문

내 코드

# 16724
import sys
sys.setrecursionlimit(10**7)


def find(x, y):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x][y] != (x, y):
        parent[x][y] = find(parent[x][y][0], parent[x][y][1])
    return parent[x][y]


def union(x1, y1, x2, y2):
    a1, a2 = find(x1, y1)
    b1, b2 = find(x2, y2)
    if a1 < b1 or (a1 == b1 and a2 < b2):
        parent[b1][b2] = (a1, a2)
    else:
        parent[a1][a2] = (b1, b2)


def dfs(x, y):
    visited[x][y] = 1
    dir = ['U', 'D', 'L', 'R']
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    idx = dir.index(table[x][y])
    nx, ny = x+dx[idx], y+dy[idx]
    if 0<=nx<n and 0<=ny<m and parent[nx][ny] != parent[x][y]:
        union(x, y, nx, ny)
        dfs(nx, ny)


n, m = map(int, input().split())
table = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

# parent 를 자기자신으로 설정
parent = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        parent[i][j] = (i, j)

visited = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            dfs(i, j)



res = set()
# print(parent)
for i in range(n):
    for j in range(m):
        find(i, j)
        if table[i][j] not in res:
            res.add(parent[i][j])

print(len(res))

처음에 단순히 DFS를 몇 번 호출하는지 세는 방법으로 문제를 풀어서 틀렸고, 두 번째는 같은 집합인지 확인하는 과정에서 마지막 유니온에 연산에 대해 부모를 업데이트 하는 것을 실시하지 않아서 틀렸다.