[Java] BOJ16929, 백준 - Two Dots

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

16929번: Two Dots

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512MB	4549	2069	1335	42.802%

문제

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

 

입력

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

 

출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

 

제한

• 2 ≤ N, M ≤ 50

 

<풀이>

그림이 많아서 복잡하게 보일 수도 있지만, 단순히 같은 색의 사이클이 존재하는지 여부만 구하면 되는 문제이다.

한 점에서 시작해서 점 세 개 이상을 거쳐 원래 점으로 돌아오는 경로를 구해야하기 때문에, BFS가 아니라 DFS를 이용하여 해결할 수 있다.

 

그래프 이론에 대한 이해만 충분하다면, 해결법 자체는 그리 어렵지 않다.

1. 해당 점에서 갈 수 있는 점들에 대해서 DFS를 수행한다.
2. 이동할 수 있는 경로 중, 이미 방문한 점이 있다면 이동거리의 차이가 4번 이상인지 확인(사이클을 만들 수 있는 점들인지 확인)
   1. 4 이상이라면 조건을 만족함을 체크하고 종료(사이클을 최소 한 개만 찾아도 되기 때문)
   2. 4 이하라면 계속해서 탐색을 진행

 

소스코드

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

public class Main {
	private static boolean[][] check;
	private static char[][] dots;
	private static int[][] d;

	private static boolean ans;

	private static int[][] move = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

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

		// 입력부
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		dots = new char[n][m];
		check = new boolean[n][m];
		d = new int[n][m];

		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				dots[i][j] = s.charAt(j);
			}
		}

		ans = false;
		// 방문하지 않은 점에 대해서 DFS 진행
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!ans && !check[i][j]) {
					dfs(i, j, 0, dots[i][j]);
				}
			}
		}

		if (ans)
			System.out.println("Yes");
		else
			System.out.println("No");

	}

	private static void dfs(int y, int x, int cnt, char c) {
		if (ans || (c == dots[y][x] && check[y][x] && cnt - d[y][x] < 3))
			return;

		d[y][x] = cnt;
		check[y][x] = true;

		for (int i = 0; i < 4; i++) {
			int nx = x + move[i][0];
			int ny = y + move[i][1];

			if (nx >= 0 && nx < dots[0].length && ny >= 0 && ny < dots.length && c == dots[ny][nx]) {
				// 이동할 수 있는 경로에 같은 색이 있을 때
				// 이미 방문한 칸이라면 이동거리가 4칸 이상인지 확인한다.
				if (check[ny][nx] && cnt - d[ny][nx] >= 3) {
					ans = true;
					return;
				}
				dfs(ny, nx, cnt + 1, c);
			}
		}
	}
}