[BOJ/16929번] Two Dots (java) : 깊이우선탐색

 

 

 

문제

 

 

 

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

 

 

 

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

 

 

Input 1

 

7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB

 

Output 1

 

Yes

 

Input 2

 

3 4
AAAA
ABCA
AADA

 

Output 2

 

No

 

 

 

 

 

풀이

 

dfs 문제에서 조금 더 생각이 필요한 문제라고 생각했다. 기존 dfs방식으로 탐색하다보면 처음 시작했던 포인트와의  연결여부가 헷갈릴 수가 있는데, 어떻게 해결할지 고민하다가 길이를 체크하는 cnt Array를 추가했다. 이후 처음 시작점에서 분기점으로 진행 길이 length 에서 cnt포인트의 값을 빼서 4보다 크면 cycle이 성립하는 것으로 정리해봤다. 이러면 바로 옆지점 이라던가 하는 에러를 방지할 수 있다. (이 부분 때문에 에러케이스가 많이 나왔다)

 

시간 복잡도는 O(n*m)

 

package com.company;

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

public class Main {

    static int n, m;
    static int[][] dirs = {{0,1},{1,0},{-1,0},{0,-1}};
    static char [][] game;
    static boolean [][] visited;
    static int [][] cnt;
    
    //static ArrayList<ArrayList<Integer>> graph;
    //static ArrayList<Integer> cntList;
    //dfs(two Dots)
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        game = new char[n][m];
        visited = new boolean[n][m];
        cnt = new int[n][m];

        for(int i=0;i<n;i++)
        {
            char [] arr = br.readLine().toCharArray();
            for(int j=0;j<m;j++)
            {
                game[i][j] = arr[j];
            }
        }
        //print(game);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(!visited[i][j])
                {
                   visited= new boolean[n][m];

                    int [] start  = {i,j};
                    if(dfs(i,j,start,1,visited))
                    {
                        System.out.println("Yes");
                        return;
                    }
                }
            }
        }
        System.out.println("No");
    }
    public static boolean dfs(int x, int y,int[]start,int length, boolean[][]visited)
    {
        if(visited[x][y])
        {
            return length-cnt[x][y]>=4;
        }
        cnt[x][y] = length;

        visited[x][y] = true;

        for(int [] dir : dirs)
        {
            int dx = x+dir[0];
            int dy = y+dir[1];
            if(dx>=0 && dy>=0 && dx<n && dy<m)
            {
                if(game[x][y]==game[dx][dy])
                    if(dfs(dx,dy,start,length+1,visited))
                        return true;

            }
        }
        return false;
    }

    //테스트
    public static void print(int [][] game)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                System.out.print(game[i][j]+" ");
            }
            System.out.println();
        }
    }
}