[백준] 16724 피리부는사나이 (C++)
피리 부는 사나이 성우는 오늘도 피리를 분다.
성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 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’의 최소 개수를 출력한다.
풀이
DFS로 지도에 존재하는 칸을 탐색하며 SAFE ZONE의 개수를 구하면 된다.
방문 처리를 진행하며 칸을 탐색하면 되는데, 두 가지 경우가 존재한다.
1. 현재 탐색을 진행하며 방문했던 칸에 다시 방문하는 경우
2. 과거에 탐색을 진행하며 방문했던 칸에 다시 방문하는 경우
1의 경우 아래 그림과 같다.
(1, 1)에서부터 탐색을 진행한다 생각해보자. 방문 처리를 하며 진행하면 마지막은 아래 그림과 같을 것이다.
(2, 3)에서 아래 화살표를 따라 이동하면 현재 탐색을 진행하며 방문했던 (3, 3)에 방문하게 된다.
이 경우 (2, 3) 또는 (3, 3)에 SAFE ZONE을 설치하면 현재 색칠된 모든 칸은 SAFE ZONE으로 이동할 수 있다.
2의 경우는 아래 그림과 같다.
(2, 2)에서부터 탐색을 진행한다 생각해보자. (2, 2)에서 아래 화살표를 따라 이동하면 (3, 2)에 방문하게 되고,
이는 과거에 탐색을 진행하며 방문했던 칸에 다시 방문하는 경우이다.
이 경우에는 기존에 설치해두었던 SAFE ZONE으로 이동할 수 있으므로 별도로 SAFE ZONE을 설치할 필요가 없다.
마지막으로 (1, 3)에서 탐색을 진행하면 1의 경우에 해당되고, 위의 그림의 경우 최소 2개의 SAFE ZONE이 필요하다.
코드
#include <iostream>
#include <vector>
using namespace std;
char map[1001][1001];
bool visited[1001][1001];
int answer = 0;
void dfs(int y, int x, vector<pair<int, int>> vec){
// 이미 방문한 적 있는 칸이라면
if (visited[y][x]){
// 이동해온 경로 중 하나로 다시 이동했다면 SAFE ZONE 추가
for (int i = 0; i < vec.size(); i++){
if (y == vec[i].first && x == vec[i].second){
answer++;
break;
}
}
return;
}
visited[y][x] = true;
vec.push_back({y, x});
// 지도에 써있는 정보에 따라 이동
if (map[y][x] == 'U'){
dfs(y-1, x, vec);
}
else if (map[y][x] == 'D'){
dfs(y+1, x, vec);
}
else if (map[y][x] == 'R'){
dfs(y, x+1, vec);
}
else if (map[y][x] == 'L'){
dfs(y, x-1, vec);
}
}
int main(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> map[i][j];
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (!visited[i][j]){
dfs(i, j, {});
}
}
}
cout << answer;
}
