[백준] 16724 피리 부는 사나이 (Python/파이썬)

<문제 링크>

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

16724번: 피리 부는 사나이

<풀이 전략>

0. DFS / BFS (+ 유니온파인드) 문제이다. 유니온 파인드에 괄호를 친 이유는 아래 설명하겠지만 유니온 파인드를 안 쓰고 bfs만으로 풀이 하는 방법도 있기 때문이다. (아래 설명)

1. 유니온 파인드 풀이

1. 주어진 그래프에서 dfs를 통해서 사이클을 확인하고 해당 사이클을 하나의 safezone 그룹으로 묶는 과정을 반복해야하는데 이 과정에서 유니온 파인드 자료구조를 사용할 수 있다.
2. 어차피 이동방향이 주어져있으므로 dfs를 이용해 경로대로 쭉 탐색하다가 이전에 방문한 영역이 등장하면(base condition) 거기서부터 union함수를 이용해 지나온 경로를 재귀적으로 union해주면 된다.
3. safezone의 개수를 세기 위해서는 넘버링을 해야하므로 find 함수 작성 시 꼭 경로 압축을 해줘야 한다.

2. BFS 풀이

1. 마찬가지로 이동방향이 주어져있으므로 bfs를 통해서 지나온 경로에 세이프존을 넘버링 해주면서 탐색을 하면 된다.
2. 단 중요한 점은, 유니온파인드와는 다르게 주어진 경로대로 나아가기만 하면 '현재 영역에서 다음 영역으로 가는 경로'만 확인하고 '다른 영역에서 현재 영역으로 접근해오는 경로'는 제대로 확인하지 못하기 때문에 그부분을 신경 써줘야 한다.

<정답 코드 - 유니온 파인드>

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 221001 16724 피리 부는 사나이

# 정답코드

# directions: 방향 정보 저장
directions = {
    'D' : (1, 0),
    'U' : (-1, 0),
    'L' : (0, -1),
    'R' : (0, 1),
}


# dfs를 통해 safezone 연결
def dfs(r, c, r_start, c_start):

    # 이전에 탐색한 곳이면
    if visited[r][c]:
        # 유니온파인드 함수를 통해 재귀적으로 safezone과 연결해준다
        merge(r, c, r_start, c_start)
        return

    # 방문 표시
    visited[r][c] = 1

    # 다음 탐색 좌표
    nr = r + directions[arr[r][c]][0]
    nc = c + directions[arr[r][c]][1]

    # 재귀적으로 탐색
    dfs(nr, nc, r_start, c_start)   

    # 함수 basecondition 도달 이후 재귀적으로 safezone 연결
    merge(r, c, r_start, c_start)
    return


# find 함수
def find(x):
    if safezone[x] != x:
        safezone[x] = find(safezone[x])
    return safezone[x]


# union 함수
def merge(r_x, c_x, r_y, c_y):

    # 2차원 배열의 좌표를 1차원 형태로 변환
    x = find((r_x * M) + c_x)
    y = find((r_y * M) + c_y)

    if x < y:
        safezone[y] = x
        
    else:
        safezone[x] = y

    return


# N, M: 배열의 크기
N, M = map(int, input().split())
# arr: 지도 배열 
arr = [list(input()) for _ in range(N)]

# visited: 방문여부 표시 배열
visited = [[0 for _ in range(M)] for _ in range(N)]
# safezone: 유니온파인드 집합 표시 배열
safezone = [i for i in range(N * M)]

# 방문하지 않은 곳이 있으면 dfs를 통해서 safezone과 연결해준다.
for r in range(N):
    for c in range(M):
        if not visited[r][c]:
            dfs(r, c, r, c)

# safezone의 개수 출력
print(len(set(safezone)))

 

<정답코드 - BFS>

* 출처 : https://only-jione.tistory.com/

# 16724 피리 부는 사나이
# 220930

'''
시작시간 15:20
종료시간 
'''

import sys
input = sys.stdin.readline
from collections import deque

N, M = list(map(int, input().split()))

arr = [list(input()) for _ in range(N)]
arrC = [[0] * M for _ in range(N)]

di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
dp = ['U', 'L', 'D', 'R']
dn = ['D', 'R', 'U', 'L']

cnt = 0
for i in range(N):
    for j in range(M):
        if arrC[i][j] == 0:
            cnt += 1
            pi, pj = i, j
            queue = deque()
            queue.append([pi, pj])
            arrC[pi][pj] = cnt
            while queue:
                pi, pj = queue.popleft()

                for d in range(4):
                    ni = pi + di[d]
                    nj = pj + dj[d]

                    if (0 <= ni < N) and (0 <= nj < M):
                        # 내 방향으로 오는 거 or 내가 가는 거
                        if arrC[ni][nj] == 0 and (arr[ni][nj] == dp[d] or arr[pi][pj] == dn[d]):
                            arrC[ni][nj] = cnt
                            queue.append([ni, nj])

print(cnt)