[백준] 16929 - Two Dots [JAVA]

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

 

1. 정답

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

public class Main {
    static char[][] arr;
    static boolean[][] visited;
    static int n, m;
    static boolean isExists = false;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static void dfs(int x, int y, int px, int py, char color, int depth) {
        visited[x][y] = true;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == color) {
                if (!visited[nx][ny]) {
                    dfs(nx, ny, x, y, color, depth + 1);
                    if (isExists) return;  
                } else if (!(nx == px && ny == py) && depth >= 4) {
                    isExists = true;
                    return;
                }
            }
        }
    }

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

        arr = new char[n][m];
        for (int i = 0; i < n; i++) {
            arr[i] = br.readLine().toCharArray();
        }

        visited = new boolean[n][m];  

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

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

 

2. 접근

 

사실 접근법을 생각못해서 힌트를 봤는데 조금 더 생각해볼껄 그랬다,,

가장 중요한 로직은 

사이클의 조건을 생각해 보는것이다. 

처음엔 방향을 조건을 잡아서 해야하나 생각했는데 경우의 수가 너무 다양해서 포기했다

정답에서 사용한 로직은

 

1. 사이클의 경우 한 바퀴를 돌고 다시 원점으로 돌아온다.

-> startX, startY 와 현재 nx,ny가 같으면 사이클이 존재한다 (startX, starrtY는 visited 배열에 있으며)

2. 하지만 바로 직전에 조회했던 값을 다시 조회하는 경우에도 if 문이 성립할 수 있으므로 -> 이전값을 저장하는 로직 추가

3. startX, startY와 현재 nx,ny와 같으며 + 직전에 조회했던 값이 아니며 + k>=4 (k는 위의 코드에서 depth)인

경우에 사이클이 존재한다

 

-> 바로직전에 있는 값도 visited배열에 있는데 또 직전 값 변수를 사용해야 하는가? 왜 ?

DFS에서는 한 방향으로 계속 탐색하며 재귀 호출을 한다. 이때 이미 방문한 노드를 만났다고 무조건 사이클이라 판단하면, 직전 노드로 다시 되돌아오는 경우도 포함되기 때문에 잘못된 판정이 될 수 있다.
그래서 visited 배열로만 판단하지 않고, 직전 위치 (px, py)를 따로 기억해서 해당 위치는 제외시킨다.

 

1. 완전 탐색을 해야하므로 dfs 선택

2. 입력을 받아서 문자배열로 저장

3. 반복문을 돌면서 visited에 존재하지 않으면 배열을 탐색

4. 존재하면 출력 

 

-> 사이클의 정의만 잘 생각하고 구현할 수 있다면 괜찮은 문제였는데,, 사이클의 정의를 생각하지 못한 바보,,