46줄에 now_x 를 next_x로, now_y를 next_y로 바꾸시면 됩니다.

여담으로, 72줄에서 방문 배열을 초기화하지 않고도 해결하는 방법도 있으니 한번 시도해보세요.

@playsworld16 님 정말 감사합니다!!! 

말씀대로 DFS 끝나고나서 check 방문배열을 0으로 되돌려놓으니까 memset 안해줘도 되네요!

제 말의 의도는, 그 어떤 형식의 초기화도 없이 가능하다는 얘기였습니다.

memset를 이용해 초기화를 하던 것을 dfs 안으로 옮기는 것은 별 의미가 없습니다.

현재 bitstr58 님의 코드는 이 문제를 풀기에 전혀 문제가 없지만, 그것은 n, m 제한이 상당히 낮기 때문입니다.

비슷한 문제에 n, m 제한이 약 200을 넘어가면 시간초과가 될 겁니다.

최악 경우에는 한번에 n*m만큼 dfs가 수행됩니다. 이를 n * m번 반복하니, 시간복잡도는 O((nm)^2)가 되죠.

제가 말한 것은, O(nm)의 해결방법을 시도해보라는 것입니다.

혹시 제 말이 이해가 안되거나 해결을 잘 못하시겠다면 언제든지 댓글로 물어보세요.

@playsworld16 님! 알겠습니다. 자세하게 설명해주셔서 감사합니다!! 더 찾아보겠습니다. 정말 감사합니다.

먼저 감사드립니다. 

@playsworld16 님. 

O(nm) 을 개선해보라고 하셔서 모든 지점에서 DFS를 시작하지 않아야겠다고 생각이 들었습니다. 

그래서 방문 안해본 곳부터 시작하도록 한줄을 추가해서 수정 해봤습니다.  70라인의 if문 입니다. 

솔직히 이 코드가  왜 맞았다고 뜨는지 정확히 이해가 안갑니다.

어느 지점에서 시작한다음 사이클이 안 만들어지면 종료될텐데요.

방문했지만 사이클이 안만들어진 지점 중에 일부를 지나가야 사이클이 만들어지는 경우도 있지 않을까요? 

42라인에서 이미 0으로 되돌려놓기 때문에 이 부분이 가능해지는 건가요? 

42라인에서 이미 0으로 되돌려놓기 때문에 이 부분이 가능해지는 건가요? 

- 네 그렇습니다. 이렇게 되면 모든 i, j에 대해서 dfs를 돌게 되네요. 전의 코드와 별 다른게 없습니다...

방문했지만 사이클이 안만들어진 지점 중에 일부를 지나가야 사이클이 만들어지는 경우도 있지 않을까요?

- 아닙니다. 만약 그렇다면 "방문했지만 사이클이 안만들어진 지점"에서 dfs를 돌 때 사이클이 만들어집니다.

간단한 증명입니다.

A 지점을 방문했을 때 사이클이 만들어지지 않았다고 가정해봅시다. 그리고 어떤 지점 B 에 대해서 A를 지나가면 사이클이 만들어진다고 해봅시다.

A 지점의 알파벳을 x라고 하면, A를 방문하고 dfs가 종료되었을 때 A와 연결된 모든 'x 인 지점들'에 대하여 사이클을 만들 수 없다는 의미가 됩니다.

만약 B가

1) 알파벳이 x가 아니거나 연결되지 않았다면 A를 지나갈 수 없으므로 사이클을 생성할 수 없고,

2) 알파벳이 x이고 A와 연결되었다면 A에서 dfs를 돌 때 사이클이 만들어지지 않는다고 했으므로 모순입니다.

감사합니다 @playsworld16 님!

설명해주신대로 "근처의 같은 색깔"을 따라가니까, 이미 방문해본 것에 대해서 사이클을 만들 수 없었으면, 다시 고려해볼 필요가 없겠네요.

O(nm) 의 시간복잡도를 줄이는 방법에 대해 조금 더 힌트를 주실 수 있을까요? 

DFS 탐색을 시작하기 전에 check 배열을 확인하는 것과는 다른 식으로 방법을 생각해야 하나요?

"목적지를 특정하지 않고, 한 번 방문한 곳은 두 번 다시 방문하지 않는 방법(물론, 사이클을 체크하는 경우는 제외하고요)" 을 생각해보세요.

일단 맞았습니다를 받으셨으니 저나 다른 분들의 공개된 코드를 구경하는 것도 가능하겠지만, 스스로 충분히 생각해 보시는 걸 추천합니다.

알겠습니다. 답변 다시 한번 감사드립니다 @playsworld16 님!