[JAVA] 백준 16929번: Two Dots ( 초급 2-44 )

문제

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개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

출력

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

 

문제 풀이

경로에 대한 문제이기 때문에 dfs를 이용하여 해결하였다.

방문 한 적이 없는 dot을 기준으로 순회한다.

다음 dot이 현재 dot과 동일한 글자를 나타내고 있으며, 방문한 적이 없는 경우에는 dfs를 진행한다.

다음 dot이 현재 dot과 동일한 글자를 나타내고 있으며, 방문한 적이 있고, 거리의 차가 3 이상일 경우에는 "Yes" 를 프린트 하고 종료

모든 dot들을 순회하였음에도 불구하고 시스템이 종료되지 않았다면 "No"를 프린트 하고 종료한다.

 

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

public class baekjoon16929_2 {
    private static int rowSize;
    private static int colSize;
    private static Character[][] info;
    private static boolean[][] visit;
    private static int[] rowTemp = { -1, 1, 0, 0 };
    private static int[] colTemp = { 0, 0, -1, 1 };
    private static int[][] distInfo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        rowSize = Integer.parseInt(st.nextToken());
        colSize = Integer.parseInt(st.nextToken());

        info = new Character[rowSize][colSize];
        distInfo = new int[rowSize][colSize];
        visit = new boolean[rowSize][colSize];

        // dots 정보 입력
        for (int i = 0; i < rowSize; i++) {
            String temp = br.readLine();
            for (int j = 0; j < colSize; j++) {
                info[i][j] = temp.charAt(j);
            }
        }

        // 모든 행열을 순회하면서, 방문하지 않은 점을 기점으로 dfs 진행
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                if (!visit[i][j]) {
                    visit[i][j] = true;
                    dfs16929(i, j);
                }
            }
        }
        System.out.println("No");

    }

    private static void dfs16929(int currentRow, int currentCol) {
        for (int i = 0; i < 4; i++) {
            int nextRow = currentRow + rowTemp[i];
            int nextCol = currentCol + colTemp[i];

            if (nextRow >= 0 && nextCol >= 0 && nextRow < rowSize && nextCol < colSize) {
                // 종료 조건: 거리 차이가 3 이상이고, 방문한 적이 있으며, 다음 글자가 현재 글자와 동일하다면
                if (distInfo[currentRow][currentCol] - distInfo[nextRow][nextCol] >= 3 && visit[nextRow][nextCol]
                        && info[currentRow][currentCol].equals(info[nextRow][nextCol])) {
                    System.out.println("Yes");
                    System.exit(0);
                }
                // 방문한 적이 없으며, 다음글자가 현재 글자와 동일하다면 dfs 진행
                if (!visit[nextRow][nextCol] && info[currentRow][currentCol].equals(info[nextRow][nextCol])) {
                    visit[nextRow][nextCol] = true;
                    distInfo[nextRow][nextCol] = distInfo[currentRow][currentCol] + 1;
                    dfs16929(nextRow, nextCol);
                }
            }
        }
    }
}