백준 16929번
https://www.acmicpc.net/problem/16929

문제

---

생각하기

---

• DFS를 통해서 사이클을 찾으면 된다.

  • 처음에 k에 대한 길이얘기가 나와서 거기 꽂혀 있었는데, 애초에 사이클만 생각하면 되는 부분이어서 생각하지 않아도 됐었다.

동작

    private static boolean DFS(int x, int y, int preX, int preY, int depth, char color) {
        if (isVisited[x][y]) return true;
        isVisited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = dirX[i] + x;
            int nextY = dirY[i] + y;

            if (!isAbleCheck(nextX, nextY, color)) continue;

            if (nextX != preX || nextY != preY) {
                if(DFS(nextX, nextY, x, y, depth + 1, color)) return true;
            }
        }

        return false;
    } // End of DFS

DFS()를 통해 사이클이 있는지 없는지를 우선적으로 파악한다.

사이클 파악할 때 if (nextX != preX || nextY != preY) { 이부분이 핵심인데, pre 이전 좌표를 통해 current현재 좌표에서 next 다음 좌표로 갈 때 pre이 이 전의 좌표는 뒤로 가는 방향이므로, 해당 방향만을 제외하고 전진으로만 진행할 수 있도록 해준다.

이렇게 해서 if (isVisited[x][y]) return true; 이미 방문한 곳을 만나게 되면, 사이클이 있는것으로 판단해서 true를 return해서 사이클을 가지고 있는지 찾을 수 있다.

결과

코드

---

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static char[][] map;
    private static boolean[][] isVisited;
    private static int[] dirX = {0, 0, -1, 1};
    private static int[] dirY = {-1, 1, 0, 0};

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (isVisited[i][j]) continue;

                boolean flag = DFS(i, j, i, j, 1, map[i][j]);
                if (flag) {
                    sb.append("Yes");
                    return sb.toString();
                }
            }
        }

        sb.append("No");
        return sb.toString();
    } // End of solve()

    private static boolean DFS(int x, int y, int preX, int preY, int depth, char color) {
        if (isVisited[x][y]) return true;
        isVisited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = dirX[i] + x;
            int nextY = dirY[i] + y;

            if (!isAbleCheck(nextX, nextY, color)) continue;

            if (nextX != preX || nextY != preY) {
                if(DFS(nextX, nextY, x, y, depth + 1, color)) return true;
            }
        }

        return false;
    } // End of DFS

    private static boolean isAbleCheck(int nextX, int nextY, char color) {
        return nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && map[nextX][nextY] == color;
    } // End of isAbleCheck()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        isVisited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }
    } // End of input()
} // End of Main class