📙[Algo] BOJ16929. Two Dots

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

문제 요약

• N*M크기의 게임판 위에서 진행
• 점 K개 d1, …, dk로 이루어진 사이클 정의는 아래와 같다
  • 모든 k개의 점은 서로 다르다
  • k는 4보다 크거나 같다
  • 모든 점의 색은 같다
  • 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접한다.
    • 또, dk와 d1도 인접한다.
    • 두 점이 인접하다는 것은 각각 점이 들어있는 칸이 변을 공유한다는 의미
• 게임판 상태가 주어질 때, 사이클이 존재하는지 아닌지 구하라

시간 제한

• 2초

입력

• 게임판의 크기 N, M
  • 2 ≤ N, M ≤ 50
• N개의 줄에 게임판 상태가 주어진다.
  • 게임판의 상태는 점의 색을 의미
  • 점의 색은 알파벳 대문자 한 글자

출력

• 사이클이 존재하면 YES, 없다면 NO 출력

접근법

• DFS알고리즘으로 한 정점에서 출발해, 같은 색깔의 정점으로만 이동 했을 때, 지나간 정점 개수가 4개 이상이면서, 마지막 도착 정점이 출발 정점과 인접한 정점이면 true를 반환했다.
  • 이때, 반환값을 담는 변수 ret에 OR연산을 적용해서 한번 true가 반환되면 true만 반환되도록 했다.
  • 마찬가지로 한 점씩 탐색을 시작하는 이중 for문에서도 dfs 반환값에도 OR연산을 적용했다.

코드

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

public class Main {
    static int N, M;
    static char[][] arr;
    static boolean[][] visited;
    // 아래부터 움직이기 시작
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};

    static boolean dfs(int row, int col, int sr, int sc, int cnt) {
        if (cnt >= 4 && row == sr && col - 1 == sc) {
            return true;
        }

        boolean ret = false;
        int mr, mc;
        for (int dir = 0; dir < 4; dir++) {
            mr = row + delR[dir];
            mc = col + delC[dir];

            if (mr < 0 || mc < 0 || N <= mr || M <= mc
                    || visited[mr][mc] || arr[mr][mc] != arr[sr][sc]) continue;

            visited[mr][mc] = true;
            ret = ret | dfs(mr, mc, sr, sc, cnt + 1);
        }

        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new char[N][M];
        visited = new boolean[N][M];
        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = input.charAt(j);
            }
        }

        boolean ret = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = true;
                ret = ret | dfs(i, j, i, j, 1);

                for (boolean[] v : visited) {
                    Arrays.fill(v, false);
                }
            }
        }

        if (ret) System.out.println("Yes");
        else System.out.println("No");
    }
}