16724 피리 부는 사나이

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

16724번: 피리 부는 사나이

 

푸는 방법이 맞았는데 실수했다. 

나는 사이클이 생기면 ans++을 하면 된다고 생각했는데, 그럴 경우 서로 마주보는 화살표에 대해서 처리가 불가능하다고 생각했다. 근데 마주보는 화살표의 경우엔 한 칸 앞으로 갔다가 다시 돌아오면 이미 갔던 공간이기에 사이클이 성립한다. 

방문 표시를 int로 남겨서 몇 번째 단계에서 방문한 공간인지 확인할 수 있게 한다.

예쁘게 Pii를 정의해서 사용했다.

#include<bits/stdc++.h>
using namespace std;
#define Pii pair<int,int>
#define Y first
#define X second

int n,m,ans,counts=1;
int vis[1003][1003];
Pii adj[1003][1003];

//현재 단계에서 이동한 좌표인지 확인하기 위해 cnt를 인수로 받음
void DFS(Pii cur, int cnt){
    vis[cur.Y][cur.X]=cnt;
    Pii nxt = adj[cur.Y][cur.X];
    if(vis[nxt.Y][nxt.X]){
        if(vis[nxt.Y][nxt.X]==cnt) ans++;
        return;
    }
    DFS(nxt,cnt);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char x; cin>>x;
            if(x=='U') adj[i][j]={i-1,j};
            if(x=='D') adj[i][j]={i+1,j};
            if(x=='L') adj[i][j]={i,j-1};
            if(x=='R') adj[i][j]={i,j+1};
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis[i][j]) continue;
            DFS({i,j},counts++);
        }
    }
    cout<<ans;
    return 0;
}