[JAVA] 백준 16929번 : Two Dots

[16929번 : Two Dots] - Gold4

---

[ 문제 ]

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

 

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

 

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

 

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

 

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

 

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

---

[ 입력 ]

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다.

게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

 

• 2 ≤ N, M ≤ 50

---

[ 출력 ]

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

# 예제 입력 1
3 4
AAAA
ABCA
AAAA

# 예제 출력 1
Yes

# 예제 입력 2
3 4
AAAA
ABCA
AADA

#예제 출력 2
No

---

[ Code ]

import java.io.*;
import java.util.StringTokenizer;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new char[n][m];
        visited = 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++) {
                visited = new boolean[n][m];
                startY = i;
                startX = j;
                visited[i][j] = true;
                if (dfs(i, j, 0)) {
                    bw.write("Yes");
                    bw.close();
                    return;
                }
            }
        }

        bw.write("No");
        bw.close();
    }

    static boolean dfs(int y, int x, int len) {
        for (int i = 0; i < 4; i++) {
            int moveY = y + dy[i];
            int moveX = x + dx[i];

            if (isValid(moveY, moveX) && arr[startY][startX] == arr[moveY][moveX]) {
                if (!visited[moveY][moveX]) {
                    visited[moveY][moveX] = true;
                    if (dfs(moveY, moveX, len + 1)) return true;
                } else {
                    if (len >= 3 && moveY == startY && moveX == startX) return true;
                }
            }
        }
        return false;
    }

    static boolean isValid(int moveY, int moveX) {
        return moveY >= 0 && moveX >= 0 && moveY < n && moveX < m;
    }
}

- dfs로 상하좌우를 탐색한다.

- 같은 알파벳이며, 맵을 벗어나지 않는지 체크한다.

- 방문한 적이 없다면, 방문 체크한 후 dfs를 계속 진행한다.

 

- 만약, 점 세개를 이었고, 다음 위치가 처음 시작한 위치와 같다면 사이클을 생성한 것이므로, true를 반환한다.