[백준 16929번] Two Dots - java

문제 설명

1. 공의 크기 X,Y 그리고 각 공들이 chr로 주어진다(문자열로 주어진걸 chr로 받는다.)

2. 같은 문자의 공들은 서로 연결 가능하다.

3. 공을 연결하여 사이클이 완성되도록(시작점부터 다른 점을 연결해 다시 시작점까지 연결될수 있도록) 할 수 있는지 구하면 된다.

4. 사이클의 크기는 4이상이 되어야 한다(가장 작은 사이클은 4이다. 연결점이 4개이기 때문)

풀이 과정

 1. 기초적인 DFS문제에 적절한 조건을 추가한 문제이다. 난이도가 높은 편은 아니라 금방 이해할 수 있을 것이다.

 2. 기존에 수행할 수 있는 DFS에 추가로 count(4이상으로), start Dot를 저장하여 비교하면 된다.

 3. 즉 DFS를 수행하여 현재점부터 상하좌우로 이동하는 xTo, yTo를 만든 후, 그 xTo가 xStart와 같고, yTo가 yStart와 같음과 동시에 count가 4 이상이면 손쉽게 구할 수 있다.

 -> 간단히 말하자면 처음 DFS가 수행되는 위치의 점을 xStart, yStart로 잡아 두고, xTo와 yTO는 xMove = {-1, 1, 0, 0} / yMove = {0, 0, -1, 1} 을 현재위치 x y에 더해준 숫자가 된다.

 -> 그 때 DFS가 계속해서 수행되면서 만들어지는 x, y에 대해 다음 DFS를 시작할 때 xTo, yTo로 도달하는 점이 xStart, yStart이면 된다는 뜻이다.

 -> 참고로 이게 되는 이유는 현재 DFS는 이전에 체크를 완료하였기 때문이다.

 4. 코드를 보면 이해가 될 것이다. 조금 난잡하여 주석으로 설명을 기입해 두었다.

 

 

코드