[백준]16929: Two Dots - JAVA

[백준]16929: Two Dots

www.acmicpc.net/problem/16929

16929번: Two Dots

풀이

해당 게임을 알고 있다면 아주 쉽게 이해할 수 있다. 싸이클을 이루는 같은 색의 점 4개를 선택할 수 있는지 출력하는 문제이다.

 

DFS탐색을 사용해 문제를 풀었다. 싸이클을 확인하는 방법을 아래와 같이 구현하였당.

1. 첫번째로 선택한 점과 마지막에 선택한 점이 같아야 한다.
2. 선택된 점들의 개수가 4개 이상이어야 한다.

위의 조건을 만족하면 true를 반환하고, 아니면 false를 반환하도록 하였다.

 

이를 위해 첫번째 점의 좌표를 static변수로 선언해 주었다. 그리고 좌표를 따라 이동하다가 이미 방문한 지점이 첫번째 좌표와 같고 count값이 4보다 크다면 조건에 맞는 싸이클이 형성되었다는 의미이므로 true를 반환했다.

 

DFS함수의 반환값이 true라면 "Yes"를 출력하고 더 이상 탐색하지 않아도 되므로 메인 함수를 종료했다. 반복문을 도는 동안 한번도 DFS 반환값이 true가 반환되지 않으면 싸이클이 없다는 의미이므로 "No"를 출력하였다.

 

코드

import java.util.*;
 
public class Main {
    
    static int n, m;
    static char[][] board;
    static boolean[][] memo;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int firstX, firstY;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
        scan.nextLine();
        
        board = new char[n][m];
        for(int i = 0; i < n; i++) {
            String str = scan.nextLine();
            for(int j = 0; j < m; j++) {
                board[i][j] = str.charAt(j);
            }
        }
    
        boolean isCircle = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                memo = new boolean[n][m];
                firstX = i;
                firstY = j;
                if(dfs(i, j, 1)) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        
        System.out.println("No");
    }
    
    public static boolean dfs(int x, int y, int count) {        
        memo[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 && board[x][y] == board[nx][ny]) {
                if(memo[nx][ny] == false) {
                    memo[nx][ny] = true;
                    if(dfs(nx, ny, count + 1)) return true;
                } else {
                    if(count >= 4 && firstX == nx && firstY == ny) return true;
                }
            }
        }
        return false;
    }
}