[python] 백준 16724 피리 부는 사나이

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

16724번: 피리 부는 사나이

 

문제 해결

safe존을 어떻게 해야 최소로 만들 수 있는지 생각을 해봐야한다.

우선 순환하는 사이클이 있으면 하나를 무조건 만들어야한다는 생각을 가져야한다.

하지만 만약 다른 그룹으로 연결이 될 수 있는 경우도 있다.

예로들면

D	L	L
R	D	Y
U	R	U

 

다음과 같은 경우

사이클이 존재하면서 가장 왼쪽 아래있는 'U'는 사이클에 연결이 되므로 safe존은 하나면 충분하다.

따라서 다른 사이클로 연결되는 경우 사이클을 굳이 만들 필요가 없다.

 

CODE

import sys
input = sys.stdin.readline


def dfs(x,y,num):
    global answer
    if visited[x][y]:
        if visited[x][y] == num: # 순환하면 safe존을 만들어야하고 다른 곳으로 연결이 되면 다른 곳으로 이동하면 되므로 굳이 만들 필요 없음
            answer += 1
        return
    visited[x][y] = num
    dir = direction.index(board[x][y])
    dfs(x + dx[dir], y + dy[dir], num)

if __name__ == "__main__":
    n, m = map(int, input().split())
    board = [list(input().rstrip()) for _ in range(n)]
    visited = [[0 for _ in range(m)] for _ in range(n)]
    direction = ['L', 'R', 'U', 'D']
    dx = [0,0, -1, 1]
    dy = [-1, 1, 0, 0]
    answer = 0
    idx = 1
    for i in range(n):
        for j in range(m):
            if not visited[i][j]:
                dfs(i,j,idx)
                idx += 1
    print(answer)