[BOJ] #16724 피리 부는 사나이

 

 

🌱 문제

16724번: 피리 부는 사나이

 

🌱 풀이

0. 기본 로직

safe_zone = []
idx = 1
for i in range(n):
    for j in range(m):
        if visited[i][j] == False:
            dfs(board, i, j, visited)
            idx += 1

• 방문하지 않은 노드를 돌면서 dfs 탐색을 합니다.
• dfs 함수에서 무조건 하나의 사이클이 찾아지므로 dfs함수를 수행하고 나오면 idx 값을 증가시킵니다.

 

1. dfs 함수

def dfs(board, x, y, visited):
    global idx
    if x < 0 or y < 0 or x > n - 1 or y > m - 1:
        return 0

    if visited[x][y] != False:
        if visited[x][y] == idx:
            safe_zone.append((x, y))
        return 1

    visited[x][y] = idx
    dx, dy = movements[board[x][y]]
    nx, ny = x + dx, y + dy
    dfs(board, nx, ny, visited)

• 방문 처리를 현재 돌고 있는 사이클의 번호인 idx로 표시합니다.
• 이때 입력받은 방향(D, U, L, R)에 따라 dfs 탐색을 했을 때, 이미 방문한 노드라면 사이클이 완성된 것입니다.
• 이미 방문한 노드의 방문처리된 값(idx)이 현재 돌고 있는 사이클의 번호와 같다면 새로운 사이클이 만들어진 것이므로 safe_zone에 현재 위치를 추가합니다. 그렇지 않으면 이미 만들어진 사이클에 현재 위치가 포함되어야 하는 것이므로 safe_zone에 추가하지 않고 리턴합니다.

 

🌱 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 16724 피리 부는 사나이

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())

board = []
for _ in range(n):
    board.append(list(map(str, input().rstrip())))

# 방향 설정
movements = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
visited = [[False] * m for _ in range(n)]

def dfs(board, x, y, visited):
    global idx
    if x < 0 or y < 0 or x > n - 1 or y > m - 1:
        return 0

    if visited[x][y] != False:
        if visited[x][y] == idx:
            safe_zone.append((x, y))
        return 1

    visited[x][y] = idx
    dx, dy = movements[board[x][y]]
    nx, ny = x + dx, y + dy
    return dfs(board, nx, ny, visited)

safe_zone = []
idx = 1
for i in range(n):
    for j in range(m):
        if visited[i][j] == False:
            dfs(board, i, j, visited)
            idx += 1

print(len(safe_zone))