Two Dots=========

📍 문제 설명

https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

💡 접근

모든 좌표에 대해서 상하좌우로 뻗어나간 후 사이클이 만들어지는지 확인하고 만들어지면 바로 끝내버리면 되는 문제

문제 조건에서 사이클은 점이 현재 3개 이상 연결되어 있고 다음 지점이 첫 지점이면 사이클이 된다.

 

👩‍💻 코드

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

public class Main {
    static int n, m, v, e, k, r, answer, cnt, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE, firstX, firstY;
    static int[] arr, dx = {1,0,-1,0}, dy = {0,-1,0,1};
    static long[] dp;
    static char[][] board, clone;
    static boolean[][] visited;
    static ArrayList<String> list;
    static TreeSet<Character> set;
    static StringBuilder sb;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new char[n][m];
        for(int i = 0; i < n; i++) {
            String[] s = br.readLine().split("");
            for (int j = 0; j < s.length; j++) {
                board[i][j] = s[j].charAt(0);
            }
        }

        //모든 좌표에 대해서 사이클 가능한지 확인인
       for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                firstX = i;
                firstY = j;
                visited = new boolean[n][m];
                visited[i][j] = true;
                T.solution(i, j, 1);
            }
        }
        System.out.println("No");
    }

    private void solution(int x, int y, int cnt) {
        //4방향에 대해서 재귀 호출
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<0 || ny<0 || nx>=n || ny>=m || board[x][y] != board[nx][ny]) continue;

            if(!visited[nx][ny]) {
                visited[nx][ny] = true;
                solution(nx, ny, cnt+1);
            }
            //방문했던 곳이면 사이클인지 확인하고 맞으면 끝내기
            else {
                if(nx == firstX && ny == firstY && cnt >= 4) {
                    System.out.println("Yes");
                    System.exit(0);
                }
            }
        }
    }


}