[JAVA] 백준 16929 - Two Dots

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

16929번: Two Dots

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static char[][] arr;
    static boolean[][] visit;
    static int n, m;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int startX, startY;

    public static void dfs(int x, int y, char color, int cnt) {
        if (cnt >= 4 && x == startX && y == startY) { // 변이 네개 이상이고 처음 위치와 동일하다면
            System.out.println("Yes");
            System.exit(0);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m || visit[nx][ny] || color != arr[nx][ny]) continue;

            visit[nx][ny] = true;
            dfs(nx, ny, color, cnt + 1);
            visit[nx][ny] = false;

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new char[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = str.charAt(j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                startX = i;
                startY = j;
                char color = arr[i][j];
                dfs(i, j, color, 1);
            }
        }
        System.out.println("No");
    }
}

 

 

dfs로 같은 색상일 경우 탐색해 나가다가 시작점으로 다시 돌아오면 사이클이다. 

이 때 사이클일 때 변의 개수가 무조건 4이상이여야 하므로 카운트가 4이상인지 체크해줘야한다. 이걸 안해서 좀 헤맸다ㅠㅠ