[백준] 16929번 Two Dots DFS로 풀어보기 (싸이클을 어떻게 구현할까?) : Programming Story

1. 문제

1) 링크

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

2) 문제

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

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

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

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

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

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

3) 입력

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

4) 출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

더 자세한 문제의 사항은 위 링크에서 확인해보자

2. 풀이

이 문제는 그래프 문제의 일종으로, DFS로 풀 수 있다.

사이클을 만드려면

최소 위의 그림처럼 4개가 이어져야 한다. 생각을 해보면 이는 전칸과 다른 칸으로 이동하다가, 이미 방문한 노드를 다시 방문하면 사이클이 존재한다는 것으로 생각할 수 있다.

이전칸과 다른 칸으로 이동해야 하는 이유는 1-2-1의 노드 순서대로 방문했을 때, 이미 방문한 노드를 다시 방문한 것이지만 싸이클이 만들어지지 않기 때문이다. 따라서 이는 DFS를 돌면서 전의 노드를 방문했으면 true를 return하고 아니면 인접해있는 노드들을 살펴보는 식으로 진행할 수 있다.

이 문제의 dfs 함수의 원형을 살펴보자.

static boolean dfs(int prev_x, int prev_y, int x, int y, char color)

prev_x: 이전 node의 행

prev_y: 이전 node의 열

x: 현재 node의 행

y: 현재 node의 열

color: 색깔

위와 같다. 여기서 prev_x, prev_y가 있는 이유는 전의 노드를 다시 방문하지 않기 위함이다 (싸이클이 아니므로!)

전의 노드와 같지 않다는 조건과 다음 해당 노드가 범위 안에 있다는 조건을 판단해서 인접하는 노드에 재귀함수를 부르는 식이다. 돌고 돌아 인접하는 노드가 전에 방문된 노드라면 싸이클이 완성이 되는 것이다.

위의 알고리즘을 코드화시키면,

static boolean dfs(int prev_x, int prev_y, int x, int y, char color){
      if (check[x][y]) return true;
        check[x][y]=true;
        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){
                if ((!(nx==prev_x && ny==prev_y)) && a[nx][ny]==color){
                    if (dfs(x, y, nx, ny, color)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

위의 코드와 같다.

다음으로는 위의 dfs 함수를 호출하고 Yes/No 판단하는 부분의 알고리즘을 살펴보겠다.

 for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                boolean ok=false;
                if (!check[i][j]){
                    ok=dfs(-1,-1, i, j, a[i][j]);
                   
                }
                if (ok){
                    System.out.println("Yes");
                    System.exit(0);
                }
            }
        }

모든 for문을 돌면서 아직 check가 false 것에 한하여 dfs 함수를 호출한다. 처음 호출할 경우에는 prev_x와 prev_y의 값이 의미가 없기 때문에 i와 j와 겹칠일 없는 -1로 준비했다. dfs함수를 호출하면 boolean의 값을 return하게 되는데 그것이 true이면 "Yes"를 출력하고 exit을 하게 된다.

모든 과정이 끝난 후에도 exit이 안되었다는 것은 싸이클이 완성되지 않았다는 것이므로 "No"를 출력하면 된다.

다음은 위의 모든 과정을 종합한 전체 코드이다.

import java.util.*;

public class Main{
    public static char[][]a;
    public static boolean check[][];
    static int n;
    static int m;
    public final static int[] dx = {0,0,1,-1};
    public final static int[] dy = {1,-1,0,0};
    static boolean dfs(int prev_x, int prev_y, int x, int y, char color){
      if (check[x][y]) return true;
        check[x][y]=true;
        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){
                if ((!(nx==prev_x && ny==prev_y)) && a[nx][ny]==color){
                    if (dfs(x, y, nx, ny, color)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
         n=sc.nextInt();
         m=sc.nextInt();
        a=new char[n][m];
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<m; j++){
                a[i][j]=s.charAt(j);
            }
        }
        check=new boolean[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                boolean ok=false;
                if (!check[i][j]){
                    ok=dfs(-1,-1, i, j, a[i][j]);
                   
                }
                if (ok){
                    System.out.println("Yes");
                    System.exit(0);
                }
            }
        }
        System.out.println("No");
    }
}