Baekjoon 16724. 피리 부는 사나이 / Python

알고리즘 설명

문제 설명

• 어느 곳에 있어도, 방향을 따라 이동하면 SAFE ZONE으로 이동할 수 있는 SAFE ZONE의 최소 갯수를 찾는 문제
• 처음엔 모든 지점을 dp로 활용하려고 했으나, union-find 알고리즘을 이용하면 손쉽게 풀린다는 것을 깨달았다.알고리즘 설명모든 칸을 순회하는 방식은 dp풀이와 같지만, 같은 지점으로 모이는 좌표들을 union find 알고리즘을 이용하여 하나의 집합으로 묶는다는 점에서 다르다.
  dp와 bfs를 이용하여 풀이한다면, 시간복잡도는 O(n * m)으로 같지만, 탐색의 과정에서 bfs는 O(4), union-find는 O(1)로 4배 정도 차이가 난다.

from collections import deque

direction = {
    'D': [0, 1],  # 아래
    'L': [-1, 0],  # 왼쪽
    'R': [1, 0],  # 오른쪽
    'U': [0, -1]  # 위
}

n, m = map(int, input().split())
arr = [list(input().strip()) for _ in range(n)]  # 지도 정보

visited = [[False] * m for _ in range(n)]  # 각 칸의 방문 여부
safe_zone_count = 0  # SAFE ZONE의 수를 세기 위한 변수

# BFS 함수
def bfs(start_x, start_y):
    q = deque([(start_x, start_y)])
    visited[start_y][start_x] = True
    while q:
        x, y = q.popleft()
        dx, dy = direction[arr[y][x]]
        nx, ny = x + dx, y + dy
        if 0 <= nx < m and 0 <= ny < n and not visited[ny][nx]:
            visited[ny][nx] = True
            q.append((nx, ny))

# 모든 칸을 순회하며 SAFE ZONE을 찾는 과정
for y in range(n):
    for x in range(m):
        if not visited[y][x]:
            bfs(x, y)
            safe_zone_count += 1  # 새로운 SAFE ZONE을 발견한 경우 카운트

print(safe_zone_count)