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

1. 문제

16724번: 피리 부는 사나이

2. 개요

구역마다 미리 설정된 방향이 존재하는 지도가 있다. 설정된 방향대로만 이동이 가능하다.

이 지도 내에 SAFE ZONE을 최소한으로 설치하려 한다.

어느 구역에 있더라도 SAFE ZONE으로 갈 수 있도록 하는 SAFE ZONE의 최소 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

SAFE ZONE을 사이클 내부에 1개씩 만들면 최소 개수가 된다.

방문처리할 인덱스를 가지고 아직 방문하지 않은 구역부터 DFS를 수행한다.

방문한 구역에는 해당 인덱스를 남겨 방문처리를 한다.

DFS중 만약 이미 방문된 구역을 만났다면 방문한 구역의 인덱스로 방문처리하며 빠져나온다.

DFS가 종료되었다면 이 인덱스를 하나씩 저장한다.

모든 구역에 대한 탐색이 종료된 후, 중복을 제외한 저장된 인덱스의 개수를 출력한다.

3-2. Python

import sys

sys.setrecursionlimit(10000000)

direction = {'U' : [-1, 0], 'L' : [0, -1], 'D' : [1, 0], 'R' : [0, 1]}
answer = 0

N, M = map(int, sys.stdin.readline().split())

visited = [[0 for _ in range(M)] for _ in range(N)]

board = []

for i in range(N):
    board.append(list(sys.stdin.readline().rstrip()))

def DFS(y, x, cnt):
    nextY, nextX = y + direction[board[y][x]][0] , x + direction[board[y][x]][1]

    if visited[nextY][nextX] != 0:
        visited[y][x] = visited[nextY][nextX]
        return visited[nextY][nextX]
    
    visited[nextY][nextX] = visited[y][x]
    DFS(nextY, nextX, cnt)
    visited[y][x] = visited[nextY][nextX]
    return visited[y][x]

safezone = set()
cnt = 1
for i in range(N):
    for j in range(M):
        if visited[i][j] == 0:
            visited[i][j] = cnt
            safezone.add(DFS(i, j, cnt))
            cnt += 1

print(len(safezone))

3-3. C#

namespace boj_16724
{
    internal class Program
    {
        static int[,] visited;
        static char[,] board;
        static Dictionary<char, int[]> dir;

        static void Main(string[] args)
        {
            dir = new Dictionary<char, int[]>()
            {
                {'U', new int[] {-1, 0} },
                {'L', new int[] {0, -1} },
                {'D', new int[] {1, 0} },
                {'R', new int[] {0, 1} },
            };

            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            visited = new int[N, M];
            board = new char[N, M];

            for (int i = 0; i < N; i++)
            {
                string row = Console.ReadLine();
                for (int j = 0; j < M; j++)
                {
                    board[i, j] = row[j];
                }
            }

            HashSet<int> safezone = new HashSet<int>();
            int cnt = 1;
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (visited[i, j] == 0)
                    {
                        visited[i, j] = cnt;
                        safezone.Add(DFS(i, j, cnt));
                        cnt++;
                    }
                }
            }

            Console.WriteLine(safezone.Count);
        }

        static int DFS(int y, int x, int cnt)
        {
            int nextY = y + dir[board[y, x]][0];
            int nextX = x + dir[board[y, x]][1];

            if (visited[nextY, nextX] != 0)
            {
                visited[y, x] = visited[nextY, nextX];
                return visited[nextY, nextX];
            }

            visited[nextY, nextX] = visited[y, x];
            DFS(nextY, nextX, cnt);
            visited[y, x] = visited[nextY, nextX];
            return visited[y, x];
        }
    }
}