백준 16929. Two Dots

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

16929번: Two Dots

 

dfs로 같은 색인 구슬들을 탐색하면서 순서대로 번호를 매긴다.

만약 인접한 구슬들 중 같은색이면서 (현재번호-인접구슬번호)가 3 이상이면 정의된 사이클이 존재하는 것이다.

 

예를들어 입력이 아래와 같을때 

4 4
YYYR
BYBY
BBBY
BBBY

 

(1,0)의 B부터 탐색을 시작한다고 생각해보자

우선 시작하는 곳에 1을 부여한다 

1

 

다음으로 같은 B가 아래 밖에 없으므로 아래로 이동해서 번호 2를 부여한다 

1
2

오른쪽으로 이동해 3을 부여

1
2	3

계속 깊이 우선 탐색으로 진행해서 다음과 같은 상태가 될때를 생각해보자 

1
2	3	4
	6	5

6에서 인접한 0이 아닌 숫자는 3,5가 있다.

6-5 = 1 이므로 불가능

6-3 = 3 이므로 {3,4,5,6} 이렇게 싸이클이 성립한다.