16724번 피리 부는 사나이

한양대 ERICA

Zero One Algorithm Contest 2018 문제이다.(https://www.acmicpc.net/category/detail/1981)

개인적으로 허를 찌르는 문제들이 많았다!

모르고, 못 푸는 문제가 거의 다...

좋은 문제와 좋은 해설을 제공해주신 분들에게 무척 감사하다.

문제 : https://www.acmicpc.net/problem/16724

대회 해설 : http://hellogaon.tistory.com/66

문제의

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

이 문장을 보고, '사이클 개수'를 구하는 것을 짐작할 수 있다.

다만, 완전히 도너츠 모양의 O 사이클이 아니라. 6 모양의 사이클도 될 수 있다.

그래서, 

처음 시작할 때부터, 행과 열의 좌표를 vector에 담아서, 

매번 새로운 행과 열을 받아들일 때, 그 새로운 행과 열이 vector에 있는지 검사한다.(사이클 검사)

입력 예시)

3 4

DLLL

DLLL

RRRU

답 : 1

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
bool visit[1001][1001] = { false, };
 
bool stop = false;
 
char Map[1001][1001];
 
int N = 0, M = 0;
 
int y = 0, x = 0;
 
int result = 0;
 
vector<pair<int, int> > v;
 
bool Chk(int r, int c)
{
    for (int i = 0; i < v.size(); i++)
        if (r == v.at(i).first && c == v.at(i).second) return true;
    
    return false;
}
 
void DFS(int r, int c)
{
    if (stop) return;
 
    visit[r][c] = true;
 
    v.push_back({ r, c });
 
    int nr = r; int nc = c;
 
    if (Map[r][c] == 'U') --nr;    
    else if (Map[r][c] == 'D') ++nr;
    else if (Map[r][c] == 'L') --nc;
    else if (Map[r][c] == 'R') ++nc;
 
    if (Chk(nr, nc))
    {
        stop = true;
 
        ++result;
 
        return;
    }
 
    if (!visit[nr][nc]) DFS(nr, nc);
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)    
            cin >> Map[i][j];
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            stop = false;
 
            if (!v.empty()) v.clear();
 
            if(!visit[i][j]) DFS(i, j);
        }
    
    printf("%d\n", result);
 
    return 0;
}