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

16724번: 피리 부는 사나이

문제

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다. 

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
map_data = []
for _ in range(n):
    map_data.append(input())
    
arr = [i for i in range(n * m)]
ans = 0

def move(num):
    x = num // m
    y = num % m
    if map_data[x][y] == 'U':
        return (x - 1) * m + y
    elif map_data[x][y] == 'D':
        return (x + 1) * m +  y
    elif map_data[x][y] == 'L':
        return x * m + (y - 1)
    else:
        return x * m + (y + 1)

def find_cycle(num):
    global ans
    
    if arr[num] != num: # 이미 방문한 칸
        return
    nx = num
    while True:
        nx = move(nx)
        if arr[nx] == num:   # 사이클 완성
            ans += 1
            return
        else: 
            if arr[nx] != nx:   # 다른 사이클 만남
                return
        arr[nx] = num
       
for num in range(n*m):
    find_cycle(num)

print(ans)

arr 배열에 처음에는 본인의 인덱스를 저장해놓는다. 

find_cycle 함수를 실행하면 map_data에 저장된 정보에 따라 움직이며 arr 배열의 값들을 처음 사이클이 시작된 지점의 인덱스로 바꾼다. 그러므로 이미 방문한 지점의 arr 배열의 값은 본인이 아닐 것이다. 따라서 find_cycle 함수의 앞부분에 이미 방문한 칸이면 함수를 리턴하도록 한 것이다. 이동하다가 arr 배열의 값이 처음 시작점의 인덱스와 같다면 사이클이 완성된 것이므로 ans 값을 1 증가시켜주고 리턴한다. 이동하다가 다른 사이클을 만나면 더이상 갈 수 없는 것이므로 그때도 리턴한다.