[BOJ/백준][Gold2] 16724 : 피리 부는 사나이 (C++)

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

16724번: 피리 부는 사나이

 

[난이도] Gold2
[유형] DFS

[풀이]
지도 밖으로 나가는 입력이 주어지지 않으므로
사이클을 찾아서 총 사이클의 개수를 세주면 됩니다.
dfs를 이용해서 현재 방문중이면 visit[y][x]=1로 체크하고
만약 다음 노드가 1로 체크되어 있다면 사이클을 찾은 것이므로 정답에 1을 더해줍니다.
또한 방문을 마칠때는 visit[y][x]=2로 체크해주어야 합니다.
왜냐하면 이미 발견되어 카운팅된 사이클로 접근하는 경우에는 이미 그 사이클에 쉼터가
존재하므로 카운팅을 해줄 필요가 없기 때문입니다. 이를 구분하기 위해 이미 쉼터에 갈 수 있는
노드들은 2로 체크해주었습니다.

 

#include <cstdio>
int N,M,ans;
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1},map[1000][1000];
int visit[1000][1000];
void dfs(int y,int x){
    visit[y][x]=1;
    int ny=y+dy[map[y][x]],nx=x+dx[map[y][x]];

    if(visit[ny][nx]==1) ans++;
    if(visit[ny][nx]==0) dfs(ny,nx);
    visit[y][x]=2;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char c;
            scanf(" %c",&c);
            if(c=='U') map[i][j]=1;
            else if(c=='R') map[i][j]=2;
            else if(c=='L') map[i][j]=3;
        }
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            if(visit[i][j]==0) dfs(i,j);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/16724.cpp