[백준 16929번] Two Dots

문제

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"를 출력한다.

제한

2 ≤ N, M ≤ 50

입력

---

정답

점들을 배열에 담아서 저장한다
사이클이 되는 경우는

• 길이가 4이상

• 주변 배열값이 시작지점과 같을때
  이다.
  이 말은

• 깊이탐색이 4번이상(재귀함수가 4번 호출된 상태)

• 주변에 탐색할수 있는 배열중에 시작지점의 인덱스값과 같을때 이다.

처음에는 모든 배열을 전체 순환하면서 각 점마다 깊이 탐색을 해야하나 싶었는데 내 생각으로는 전체를 순회하면서 탐색하는 방법밖에는 없었다. 혹시 좀더 좋은 방법이 있다면 댓글로 남겨주길

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class Main {
    public static class Graph{
        int[] di= {0,0,-1,1};
        int[] dj = {-1,1,0,0};
        int n,m;
        //map 배열
        char [][] map;
        public Graph(int n, int m) {
            map = new char[n][m];
            this.n=  n;
            this.m = m;
        }
        //싸이클탐색
        public void cycle() {
            //배열 전체 순환하면서 체크
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    char c = map[i][j];//탐색할 문자 찾기
                    boolean [][] visited = new boolean[n][m];
                    int k=0;
                    DFS(i,j,i,j,c,visited,k);
                }
            }
            System.out.println("No");
        }
        //깊이탐색
        public void DFS(int si, int sj, int i,int j, char c,boolean[][] visited, int k) {
            //현재 방문한 값 체크
            visited[i][j]=true;
            //새로 방문했으니 k증가
            k++;
            //주변 배열 값 체크 
            //주변 배열 값이 시작 지점인지 체크
            for(int x=0;x<4;x++) {
                int ni = i+di[x];
                int nj = j+dj[x];
                //사이클 지점이면 yes로 끝
                if(ni>=0 && nj>=0 && ni<n && nj<m) {
                    if(ni == si && nj == sj && visited[ni][nj]==true && k>=4) {
                        System.out.println("Yes");
                        System.exit(0);
                    }
                    if(visited[ni][nj]!=true && c == map[ni][nj]) {
                        DFS(si,sj,ni,nj,c,visited,k);
                    }
                }
            }
        }
        //map 생성 함수
        public void addmap(int index, String array) {
            for(int i=0;i<array.length();i++) {
                map[index][i] = array.charAt(i);
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] NM = br.readLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        Graph g = new Graph(n,m);

        for(int i=0;i<n;i++) {
            String array = br.readLine();
            g.addmap(i,array);
        }

        //사이클 깊이탐색
        g.cycle();

        br.close();
        bw.flush();
        bw.close();
    }
}