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

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

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

[난이도] Gold2

[유형] DFS

[풀이]

지도 밖으로 나가는 입력이 주어지지 않으므로

사이클을 찾아서 총 사이클의 개수를 세주면 됩니다.

dfs를 이용해서 현재 방문중이면 visit[y][x]=1로 체크하고

만약 다음 노드가 1로 체크되어 있다면 사이클을 찾은 것이므로 정답에 1을 더해줍니다.

또한 방문을 마칠때는 visit[y][x]=2로 체크해주어야 합니다.

왜냐하면 이미 발견되어 카운팅된 사이클로 접근하는 경우에는 이미 그 사이클에 쉼터가

존재하므로 카운팅을 해줄 필요가 없기 때문입니다. 이를 구분하기 위해 이미 쉼터에 갈 수 있는

노드들은 2로 체크해주었습니다.

#include 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

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

from http://leesh111112.tistory.com/335 by ccl(A) rewrite - 2021-10-19 00:26:43