✓

태그:

CLASS 5

유향 그래프에 존재하는 사이클의 개수를 어떻게 구했었죠…??

풀이 비스무리한거 보기

2차원 보드의 각 칸마다 매 턴당 움직이는 방향이 적혀있을 때, 이 보드의 어느 칸에서 시작해도 SAFE ZONE에 들어갈 수 있도록 SAFE ZONE을 설치하는 최소 개수를 구하는 문제입니다. 보드 바깥으로 나가는 방향이 주어지지 않는다는 조건을 고려하면 이 문제는 그래프에 존재하는 사이클의 개수를 구하는 문제입니다. 사이클을 이루지 않는 노드는 사이클로 향하는 길을 항상 가지게 됩니다.

이는 스택을 사용하여 구현할 수 있습니다. 아무 칸이나 시작해서 주어진 방향대로 스택에 칸을 추가하되, 이 스택에 이미 존재하는 칸이라면 이전에 발견하지 않은 사이클을 찾은 것이므로 카운트를 하나 늘리고 스택에 있는 모든 칸은 방문한 칸으로 표시합니다. 그리고 또 다른 경우는 이미 방문한 칸인 경우입니다. 이 경우는 이미 찾은 경우이므로 스택에 있는 모든 칸을 방문했다고 표시하는 것 외에는 아무것도 하지 않습니다. 이를 모든 칸에 대해 반복하면 문제의 답인 사이클의 개수를 구할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-14 23:18:59

---