알고리즘 풀이 - 백준 16929(Two Dots, 그래프(DFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

문제 설명은 위의 더보기를 클릭

 

 

2. 풀이

 

이 문제는 단순한 DFS 문제임에도 엄청 많이 틀렸다. 알고 보니 "Yes"라고 출력해야 하는데 "YES"로 출력하고 있어서 틀렸다..

부디 다른 분들은 이런 실수 하지 않기를 바라며...

 

이 문제는 같은 색상으로 이루어진 정점을 4개 이상 탐색하였을 때, Cycle이 발생하면 "Yes"를 출력하고 아니면 "No"를 출력한다.

우선 Cycle을 찾아내기 위해서는 기존에 이미 방문된 정점을 다시 한 번 방문하는 절차가 필요하다.

즉, DFS를 탐색을 수행하며 현재 탐색 중인 위치를 방문 완료로 표기하고 Cycle을 발견할 때까지 DFS를 통해 탐지를 수행하면 된다.

 

처음에 이 문제를 풀 때는, 방문 완료를 표기하면서 Cycle이 있고 최초 방문 지점으로 돌아갔을 때 4회 이상 정점을 방문한 경우에만 true를 반환하고 이외의 경우에는 false를 반환하며 다시 방문 완료 표기를 해제하였다.

 

그런데, 실제로 탐색을 수행 중일 때는 Cycle이 발견되지 않는다면 그 도중에 탐색된 모든 위치의 정점을 다시 방문 해제를 표기하여 재방문을 시도할 이유가 없다!

아래의 그림을 보자.

 

위의 그림에서 Cycle이 있는 곳은 파란색의 4개의 칸이 연결되어 있는 부분 이외에는 없다!

즉, 주황색 부분은 DFS로 탐색하고 나면 어차피 그 안에 모든 부분에 Cycle은 발견되지 않았다는 것이므로 추가 탐색이 완전히 불 필요한 상태가 된다.

이 내용을 기반으로 전체 시간 복잡도를 더 줄여볼 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 전체에서 모두 탐색을 수행 시작하는 경우

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

public class Main{
    static StringTokenizer st;
    static int N;
    static int M;
    static String[] dots;
    static boolean[][] visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};

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

        // 주어진 값들 저장
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dots = new String[N];
        visited = new boolean[N][M];

        for(int i=0; i < N; i++){
            dots[i] = br.readLine();
        }
        
        // 각 위치에서 DFS 탐색 수행
        for(int i=0; i < N; i++){
            for(int j=0; j < M; j++){
                if(dfs(i, j, i, j, 1)){
                    System.out.println("Yes");
                    System.exit(0);
                }
            }
        }
        System.out.println("No");

        br.close();
    }

    private static boolean dfs(int start_y, int start_x, int y, int x, int pass){
    
        // 이미 방문된 곳이면서, 4번 이상 방문했고 처음 위치로 되돌아갔다면 true 반환
        if(visited[y][x]){
            if(y == start_y && x == start_x && pass >= 4) return true;
            else return false;
        }

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

            // 범위 안에 있고 같은 색상인 경우 dfs 추가 탐색
            if(!(0 <= ny && ny < N && 0 <= nx && nx < M)) continue;
            if(dots[y].charAt(x) == dots[ny].charAt(nx)){
                if(dfs(start_y, start_x, ny, nx, pass+1)){
                    return true;
                }
            }
        }
        visited[y][x] = false;
        return false;
    }
}

 

② 개선된 코드

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

public class Main{
    static StringTokenizer st;
    static int N;
    static int M;
    static String[] dots;
    static boolean[][] visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};

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

        // 주어진 값들 저장
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dots = new String[N];
        visited = new boolean[N][M];

        for(int i=0; i < N; i++){
            dots[i] = br.readLine();
        }

        // 각 위치에서 DFS 탐색 수행
        for(int i=0; i < N; i++){
            for(int j=0; j < M; j++){
                
                // 이전에 방문했다면 그 색상이 지나는 인접 정점은 전부 Cycle이 없는 것
                if(visited[i][j]) continue;
                if(dfs(-1, -1, i, j)){
                    System.out.println("Yes");
                    System.exit(0);
                }
            }
        }
        System.out.println("No");

        br.close();
    }

    private static boolean dfs(int by, int bx, int cy, int cx){

        // 기 방문된 곳이라면 Cycle이 있는 것!
        if(visited[cy][cx]){ return true; }
        visited[cy][cx] = true;

        for(int i=0; i < 4; i++){
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            // 범위 안에 있고 이전 정점으로 되돌아가는 것이 아니며, 같은 색상이면 dfs 추가 탐색
            if(!(0 <= ny && ny < N && 0 <= nx && nx < M)) continue;
            if(ny == by && nx == bx) continue;
            if(dots[cy].charAt(cx) == dots[ny].charAt(nx)){
                if(dfs(cy, cx, ny, nx)){
                    return true;
                }
            }
        }
        return false;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.