[Algorithm] 백준 16929 Two dots Java 자바

자바 연습해야겠다. 이제 자바 써야지

백준 16929 원문 링크

1. 문제

요런 식의 보드가 2차원 배열로 주어진다. 색은 알파벳으로 표현된다. 그 때 같은 색으로 사이클을 만들수 있나 없나를 묻는 문제.

다만, 사이클은 4개 이상의 점이어야 하고, 인접해야 하고, 서로 다른점이어야 하는 등의 조건이 있다.

2. 어떻게 풀었지?

dfs로 풀어야겠다고 생각했다. 사이클이라는건 같은 색의 점을 dfs로 쭉쭉 따라가다가 이미 방문한 점을 방문하는 경우 true return.

방향을 결정하는 dx, dy를 두는 그런 너낌적인 느낌의 문제였던 것 같다. dfs의 종료 조건은 만약 방문한 노드면 true return, 아니면 visited 배열을 true로 셋팅 (디폴트가 false) ~자바로 알고리즘 오랜만이라 이거 false 초기화 어케하지 하다가 보니까 원래 boolean 배열은 false로 초기화 되더군..

하다 보니까 dfs로 같은 점을 쭉쭉 따라갈 때, 이전 점을 따라가면 안되겠더라. 그래서 파라미터로 prevx랑 prevy도 같이 넘겨서, 새로운 점이 이전 점이랑 같지 않을 때만 dfs를 돌게 했다.

개인적으로 패딩 넣는게 좋아서 board를 1씩 더 크게 만들었다. ~메모리 낭빈가..?

3. 어디서 헷갈렸지?

크게 헷갈리는건 없었는데 약간 dfs 조건문 쓰는것 정도..? 이런 류의 dfs를 풀 때마다 약간 재귀를 어떻게 설계할지가 고민된다. 더 많이 풀어봐야겠지..?

4. Code

import java.util.Scanner;

public class baekjun_16919 {

    static char[][] board;
    static boolean[][] visited;
    static int n,m;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};

    public static boolean dfs(int prevx, int prevy, int startx, int starty) {

        if (visited[startx][starty]) return true;
        visited[startx][starty] = true;

        for(int i = 0; i<4; i++) {
            int newx = startx +dx[i];
            int newy = starty +dy[i];
            if (newx >= 1 && newy >=1 && newx<=n && newy<=m) {
                if ((newx != prevx || newy != prevy) && board[startx][starty] == board[newx][newy]) {
                    if(dfs(startx,starty,newx,newy)) {
                        return true;
                    };
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        board = new char[n+1][m+1];
        visited = new boolean[n+1][m+1];

        for (int i  = 1; i<=n; i++) {
            String s = sc.next();
            for(int j = 1; j<=m ; j++) {
                board[i][j] = s.charAt(j-1);
            }
        }

        for (int i  = 1; i<=n; i++) {
            for(int j = 1; j<=m ; j++) {
                boolean ans = false;
                if (!visited[i][j]) {
                    ans = dfs(0,0,i,j);
                }
                if (ans) {
                    System.out.println("Yes");
                    return;
                }

            }
        }
        System.out.println("No");
    }
}