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

문제 접근

N * M 크기의 게임 보드에서, 같은 색의 점들이 4개 이상 연결되어 만들어지는 사이클의 존재 여부를 판별하는 문제

위 문제의 경우 주어진 2차원 격자(grid)를 그래프(graph)로 해석하는 것이 포인트이다.
각 칸의 점을 하나의 정점(Vertex)으로 인접한(상하좌우)같은 색의 점들 사이의 연결을 간선(Edge)으로 볼 수 있다.

결국 이 문제는 "주어진 무방향 그래프 내에 사이클이 존재하는가?"를 묻는 전형적인 그래프 탐색 문제이다.

이러한 경로 기반의 사이클 존재 여부를 찾는 데에는 깊이 우선 탐색(DFS, Depth-First Search)이 매우 효과적인 알고리즘이다.

제약 조건

보드 크기

2 <= N, M <= 50
보드의 최대 크기는 50 50 = 2500으로, 모든 칸을 한 번씩 탐색하는 O(N M) 복잡도의 알고리즘으로 충분히 해결 가능하다

사이클 길이

k >= 4
사이클을 구성하는 점은 4개 이상이어야 한다. 격자 구조상 인접한 연결만 가능하므로, 만들어질 수 있는 가장 작은 사이클은 2 * 2형태의 사각형이다.
-> 따라서 단순히 사이클의 존재 여부만 찾아내면 이 조건은 만족된다.

문제 설계

전체 프로세스

• 입력 및 초기화: N * M과 게임 보드 상태(char[][] matrix)를 입력 받는다. 모든 점의 방문 여부를 기록할 boolean[][] visited 배열을 false로 초기화한다.
• 전체 보드 순회: (0, 0)부터 (N-1, M-1)까지 모든 점을 이중 for문으로 순회한다.
• 탐색 시작점 결정: 만약 현재 점(i, j)가 아직 방문하지 않은(!visited[i][j]) 새로운 연결 요소의 시작점이라면, 해당 점에서 DFS 탐색을 시작한다.
• 사이클 탐색(DFS): 시작된 DFS는 같은 색의 인접한 점들을 따라 깊이 들어가며 경로를 탐색한다. 탐색 중 사이클이 발견되면 즉시 탐색을 모두 중단한다.
• 결과 출력: 만약 DFS 중 사이클이 한번이라도 발견되었다면 "Yes"를 출력하고 프로그램을 종료한다. -> 모든 점을 다 순회했음에도 사이클이 발견되지 않았다면 "No"를 출력한다.

자료구조 및 함수 정의

전역 변수

• int N, M: 게임 보드의 크기
• char[][] matrix: 게임 보드의 색상 정보를 저장하는 2차원 배열
• boolean[][] visited: 각 점의 방문 여부를 기록하는 2차원 배열. 중복 탐색을 방지하고 사이클 판별에 사용된다.
• boolean isValid: 사이클 발견 시 true로 변경될 플래그 변수
• int[] dr, dc: 상하좌우 방향 탐색을 위한 배열

함수

• dfs(int row, int col, int prevR, int prevC): 사이클을 탐색하는 재귀 함수
  - row, col: 현재 탐색 중인 점의 좌표
  • prevR, prevC: 현재 점으로 오기 직전, 즉 부모 점의 좌표, 탐색이 왔던 길로 바로 되돌아가는 것을 방지하는 데 사용된다.

## 설계 근거 ### 사이클 탐색에 DFS를 사용하는 이유 문제는 **'최단경로'가 아닌 '사이클의 존재 유무'**를 묻고 있다. DFS는 하나의 경로를 따라 최대한 깊게 탐색하는 특성이 있기 때문에 경로상의 한 정점에서 이미 방문했던 과거의 정점으로 돌아가는 것에 매우 직관적이고 효율적인 알고리즘이다.

BFS는 시작점으로부터 거리가 가까운 순서대로 탐색하므로 최단 경로 찾기에 특화되어 있지만, 사이클 탐지로직을 구현하는 것에 있어서는 DFS보다 상대적으로 복잡할 수 있다.

구현 코드

초기 설정

package Algorithm.DFS.BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class gold4_16929_twoDots {

    static int N, M;
    static char[][] matrix;
    static boolean[][] visited;
    static boolean isValid;

    static int[] dr = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dc = {0, 0, -1, 1};

    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());

        matrix = new char[N][M];
        visited = new boolean[N][M];
        isValid = false;

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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dfs(i, j, -1, -1);
            }
        }

        System.out.println(isValid ? "Yes" : "No");
    }
    // ... dfs 함수 ...
}

사이클 탐색(dfs)

public static void dfs(int row, int col, int prevR, int prevC) {
	visited[row][col] = true;
	for (int dir = 0; dir < 4; dir++) {
		int nr = row + dr[dir];
		int nc = col + dc[dir];
		
		if (nr == prevR && nc == prevC) {
			continue;
		}
		
		if (check(nr, nc) && matrix[nr][nc] == matrix[row][col]) {
			if (!visited[nr][nc]) {
				dfs(nr, nc, row, col);
			} else {
				isValid = true;
				return;
			}
		}
	}
	visited[row][col] = false;
}

public static boolean check(int nr, int nc) {
	return nr >= 0 && nr < N && nc >= 0 && nc < M;
}

상하좌우 다음 탐색 지점이 prevR, prevC가 아닌 경우에만 진행
방문하지 않은 경우 방문처리하고 해당 row, col, prevR, prevC를 갱신하여 dfs를 재귀호출
방문 정점을 만난 경우 사이클이 발생한 경우이므로 isValid를 true로 바꾸고 dfs 함수를 종료
깊이 탐색을 완료했지만 사이클이 발생하지 않은 경우 이전 방문상태를 원래대로 되돌리고 다음 dfs 진행

피드백

• 모든 matrix 배열에 대해 i,j 좌표값을 기준으로 DFS를 시작할때 cycle이 발생하면 더이상 사이클 탐색을 진행할 필요가 없는데 그부분을 가지지기를 안했다. -> 사이클이 발생해도 이후 좌표들에 대한 DFS 탐색을 하게됨(비효율적)
• 원래 코드

for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		dfs(i, j, 0, 0);
	}
}

• 수정 코드

for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
    	// 수정 로직
		if (!visited[i][j]) { // 방문하지 않은 점에서만 새로운 탐색 시작
			dfs(i, j, -1, -1);
			if (isValid) { // 사이클을 찾으면 즉시 종료
				System.out.println("Yes");
				return;
			}
		}
	}
}

위와같이 반복문을 순회하면서 해당 i,j 기준으로 DFS 탐색을 통해 사이클 탐지를 진행하다 사이클이 발견되면 바로 종료하면 된다.

• 상태원복의 필요성
  기존 코드는 DFS를 진행하고 최대 깊이 도달했을 경우 사이클이 되지 않으면 이전 노드로 되돌아가 다음 탐색을 진행하고 방문했던 노드를 다시 false 처리하는 backtrack하고 있는데
  사실상 경우의 수를 고려할 필요없이 사이클이 있는지만 탐색하면 되니
  visited를 다시 되돌릴 필요없이 visited가 false인 i, j값에서 다시 탐색을 진행하면 됨

• 수정 코드

public static void dfs(int row, int col, int prevR, int prevC) {
	visited[row][col] = true;
	for (int dir = 0; dir < 4; dir++) {
		int nr = row + dr[dir];
		int nc = col + dc[dir];
		
		if (nr == prevR && nc == prevC) {
			continue;
		}
		
		if (check(nr, nc) && matrix[nr][nc] == matrix[row][col]) {
			if (!visited[nr][nc]) {
				dfs(nr, nc, row, col);
			} else {
				isValid = true;
				return;
			}
		}
	}
    // 상태 원복 코드만 제거해주면 된다.
	//visited[row][col] = false;
}

회고

기존에는 문제 조건을 확인하고 완전탐색으로도 가능할거 같으면 완전탐색으로 풀이를 하고 끝났었는데 이제는 좀더 시간이나 공간 복잡도 측면에서 최적화가 가능한지?에 대한 생각을 좀 더 해보는 단계를 가지면 좋을 것 같다.