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

문제

출처 : www.acmicpc.net/problem/16724

16724번: 피리 부는 사나이

N*M지도가 있고, 그 위에 영과일 회원들이 있다.

지도의 각 칸에는 U,D,L,R 이 쓰여있는데, (순서대로 위, 아래, 왼쪽, 오른쪽) 성우가 피리를 불기 시작하면, 영과일 회원은 자기 발 아래의 방향에 맞게 이동한다.

재훈이는 영과일 회원의 안전을 위해 SAFE ZONE을 설치할려고한다. 영과일 회원이 어디에 있던지 항상 SAFE ZONE으로 들어갈수있도록 설치하여야한다. 이때, 설치해야할 SAFE ZONE의 최소갯수를 구하는 문제다.

 

풀이

간단한 DFS로 풀리는 문제다.

문제를 읽어보면 각 칸에서 이동할수있는 방향은 하나밖에 없다는 걸 알수있다. 따라서, 어떤 위치에서 시작하던 발 아래있는 방향을 따라 움직이다보면 항상 사이클이 존재하거나 지도 밖으로 떨어진다. 

 

SAFE ZONE을 최소한으로 설치하는 방법은 크게 두가지 이다.

1. 사이클이 존재하는곳의 아무곳에나 SAFE ZONE을 설치해야함

(사이클이 존재하므로 해당 사이클의 어디에서 시작하던 항상 SAFE ZONE에 도달함)

2. 지도 밖으로 떨어지는 위치에 SAFE ZONE을 설치해야함

(어떤 위치에서 시작하던 해당 경로의 마지막이 지도밖으로 떨어지는 위치라면 해당 위치에 SAFE ZONE을 설치 함으로써 이전 경로들에 설치할 필요가 없게됨)

 

위 조건 그대로 사이클이 존재하거나, 지도 밖으로 떨어지는 위치라면 SAFE ZONE을 설치하면된다.

 

이 때, 이미 SAFE ZONE으로 향하는 경로에 SAFE ZONE을 중복해서 설치하지 않도록 주의하자 (이거 때문에 틀렸었음)

소스코드

https://github.com/devxb/JJUNalgo/blob/master/16724%20%ED%94%BC%EB%A6%AC%20%EB%B6%80%EB%8A%94%20%EC%82%AC%EB%82%98%EC%9D%B4/main.cpp

devxb/JJUNalgo