[백준] 16929. Two Dots (Java)

 

문제

16929번: Two Dots

 

 

알고리즘

그래프, 깊이우선탐색(DFS)

 

 

풀이

그래프에 같은 색으로 이루어진 사이클이 있는지 찾는 문제이다.

사이클은 점의 개수가 4보다 크거나 같아야하며 마지막 점이 출발 점과 같은 색이어야한다.

 

따라서 그래프의 각 점을 출발점으로 하여 DFS를 진행해 사이클이 발생하는 점이 있는지 확인한다.

DFS를 위한 재귀 함수의 매개변수로 시작점의 좌표, 현재 점의 좌표, 지나온 점의 개수를 전달한다.

 

함수의 흐름은 다음과 같다.

현재 점과 인접한 점 (ny, nx)에 대해

1. 인접한 점이 시작점이고, 지나온 점의 개수가 3보다 크거나 같다면 사이클이므로 Yes 출력하고 종료

2. 인접한 점을 방문하지 않았고, 색이 같다면 그 점을 현재 점으로 함수 재귀 호출

 

 

코드

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

public class Main {
	static int[] dy = { -1, 0, 1, 0 };
	static int[] dx = { 0, -1, 0, 1 };
	static int N, M;
	static boolean[][] visited;
	static char[][] board;

	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());
		board = new char[N][M];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				board[i][j] = str.charAt(j);
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited = new boolean[N][M];
				visited[i][j] = true;
				dfs(i, j, i, j, 0);
			}
		}

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

	private static void dfs(int rooty, int rootx, int y, int x, int count) {
		
		for (int d = 0; d < dy.length; d++) {

			int ny = y + dy[d];
			int nx = x + dx[d];	
			
			if (ny == rooty && nx == rootx && count + 1 >= 4) {
				System.out.println("Yes");
				System.exit(0);
			}
			
			if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx]) continue;
			if(board[ny][nx] != board[rooty][rootx]) continue;
			
			visited[ny][nx] = true;
			dfs(rooty, rootx, ny , nx, count + 1);
			visited[ny][nx] = false;
		}
	}
}