[백준] 16929번 : Two Dots

16929번: Two Dots

---

[DFS]

DFS를 이용해 A ~ Z로 이루어진 격자에서 사이클이 존재하는지 여부만 판단하면 된다.

 

사이클을 확인하는 알고리즘은 다음과 같이 작성했다.

    static boolean visit = new boolean[51][51];
    static boolean cycle;
    
    /*
    현재 방문하고 있는 정점이 이미 방문되었고, cnt가 4이상이면 cycle을 찾았다고 판단
    */
    
    static void DFS(int y, int x, int bY, int bX, int cnt){

        //현재 정점이 이미 방문한 곳 & 4개 이상을 거쳤는지?
        if(visit[y][x] && cnt >= 4){
            cycle = true;
            return;
        }

        visit[y][x] = true;
        char cur = map[y][x];

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            //범위를 넘지않고, 현재 정점의 알파벳과 동일한지? 바로 다음 정점이 이전 정점과 다른지?
            if(ny < 1 || nx < 1 || ny > n || nx > m || map[ny][nx] != cur) continue;
            if(ny == bY && nx == bX) continue;

            DFS(ny, nx, y, x, cnt + 1);
        }
    }

# Code </>

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

public class Main {

    static int n, m;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static char[][] map = new char[51][51];
    static boolean[][] visit = new boolean[51][51];
    static boolean cycle;

    static void DFS(int y, int x, int bY, int bX, int cnt){

        if(visit[y][x] && cnt >= 4){
            //System.out.println("(" + y+", " + x +") 에서 사이클 발생");
            cycle = true;
            return;
        }

        visit[y][x] = true;
        char cur = map[y][x];

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if(ny < 1 || nx < 1 || ny > n || nx > m || map[ny][nx] != cur) continue;
            if(ny == bY && nx == bX) continue;

            DFS(ny, nx, y, x, cnt + 1);
        }
    }

    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());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=m; j++)
                map[i][j] = str[j-1];
        }

        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++){
                if(!visit[i][j])
                    DFS(i, j, 0, 0, 1);
            }
        System.out.println(cycle? "Yes":"No");
    }
}