[Python] 16724 피리 부는 사나이

💻 문제 정의

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

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

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

💡 접근 및 설계

이동 방향이 정해진 그래프에서 탐색을 이어나가며 사이클이 발생하는지 확인한다.

✏️ 알고리즘 풀이

# 이동 정의 함수
def move(x, y, dir):
    if dir == "U":
        return (x-1, y)
    elif dir == "D":
        return (x+1, y)
    elif dir == "L":
        return (x, y-1)
    elif dir == "R":
        return (x, y+1)

def dfs(x, y, group):
    visited[x][y] = group
    
    nx, ny = move(x, y, graph[x][y])

    # 이동 후 아직 어느 그룹도 아니다(= 방문하지 않았다.)
    if visited[nx][ny] == -1:
        return dfs(nx, ny, group)

    # 이동 후의 그룹과 현재의 그룹이 같다. (= 사이클 발생)
    if visited[nx][ny] == group:
        return 1

    # 사이클 발생 X
    return 0

그룹 넘버를 통해 사이클을 판별한다. 방문하지 않은 점들을 통해 탐색을 이어나가면서 처음 탐색을 시작한 점을 만났을 때(즉, 그룹 넘버가 같은 점을 만났을 때) 사이클이 발생함을 알 수 있다. 따라서 Safe Zone을 설치할 수 있다.

🗒️ 최종 제출 코드 (Python3 제출)

# 16724 피리 부는 사나이

# 이동 정의 함수
def move(x, y, dir):
    if dir == "U":
        return (x-1, y)
    elif dir == "D":
        return (x+1, y)
    elif dir == "L":
        return (x, y-1)
    elif dir == "R":
        return (x, y+1)

def dfs(x, y, group):
    visited[x][y] = group
    
    nx, ny = move(x, y, graph[x][y])

    # 이동 후 아직 어느 그룹도 아니다(= 방문하지 않았다.)
    if visited[nx][ny] == -1:
        return dfs(nx, ny, group)

    # 이동 후의 그룹과 현재의 그룹이 같다. (= 사이클 발생)
    if visited[nx][ny] == group:
        return 1

    # 사이클 발생 X
    return 0

N, M = map(int, input().split())
graph = [list(input()) for _ in range(N)]

visited = [[-1] * M for _ in range(N)] # 방문정보(그룹 넘버) 저장

ans = 0 # 정답
group = 0 # 그룹 넘버 0, 1, 2, ... 
for x in range(N):
    for y in range(M):  
        if visited[x][y] == -1:
            ans += dfs(x, y, group) # 탐색을 통해 같은 그룹 판별, 해당 그룹에 safe zone 1개 두기
            group += 1 # 다음 그룹

print(ans)

---

💭 오늘의 회고

-