[JAVA] 백준 16929번: Two Dots

요구사항

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 확인하라.

 

문제 해설

최소거리를 확인하는 문제가 아니기 때문에 dfs를 이용하였다.

기존의 dfs 문제와 다른점이 있었다면, 사이클 성립을 확인하기 위해 방문한 곳을 확인하는 로직이 필요하다는 것이었다.

 

사이클이 성립하려면 최소 4개의 점을 방문하여야 한다는 점을 이용하여 해결하였다.

1. 점을 하나씩 이동할 때마다 dist ary 해당 좌표의 값을 1씩 늘렸다.

2. 해당 점에서 상, 하, 좌, 우의 존재하는 점이 방문한 좌표이고 dist값의 차이가 4 이상이면 cycle이 성립한다고 볼 수 있다.

 

 

import java.util.Arrays;
import java.util.Scanner;

public class baekjoon16929 {
    static Boolean isTrue = false;
    static boolean[][] visit;
    static char[][] info;
    static int[][] dist;
    static int n;
    static int m;
    static int[] aryW = { -1, 1, 0, 0 };
    static int[] aryH = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        info = new char[n][m];
        dist = new int[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String temp = sc.next();
            for (int j = 0; j < m; j++) {
                info[i][j] = temp.charAt(j);
                visit[i][j] = true;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visit[i][j]) {
                    visit[i][j] = false;
                    permutation(i, j, 1);
                }
            }
        }
        if (isTrue) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }

    static void permutation(int h, int w, int cnt) {
        for (int i = 0; i < 4; i++) {
            int newH = h + aryH[i];
            int newW = w + aryW[i];
            // 좌표가 범위내에 있으며, 색깔이 같을 때
            if (newH >= 0 && newW >= 0 && newH < n && newW < m && info[newH][newW] == info[h][w]) {

                // 거리 차가 4 이상이고, 방문한 적이 있으면
                if (cnt - dist[newH][newW] >= 4 && visit[newH][newW] == false) {

                    isTrue = true;
                } else if (visit[newH][newW]) {

                    dist[newH][newW] = cnt;
                    visit[newH][newW] = false;
                    permutation(newH, newW, cnt + 1);
                }
            }
        }

    }

}