백준(BOJ) 16929번 Two Dots

알고리즘 풀이/백준(Boj) 2020. 3. 13. 16:42

16929번: Two Dots

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

www.acmicpc.net

풀이 :

DFS를 통해 사이클이 발견 시 true를 반환하도록 ccheck 함수를 만들었다.

이때 by bx는 이전 y,x를 나타내는데 if (ny == by && nx == bx )는 뛰어넘도록 만들어 주었다.

by와 bx가 없다면 오른쪽으로 갔다가 바로 왼쪽으로 가는 경우도 사이클로 판단하기 때문이다

코드 ( C++ )

백번 열번 백번 열번