Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.
각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.
다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.
점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.
게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.
첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.
사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.
3 4
AAAA
ABCA
AAAA
Yes
3 4
AAAA
ABCA
AADA
No
4 4
YYYR
BYBY
BBBY
BBBY
Yes
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB
Yes
2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ
No
이 문제는 DFS 알고리즘을 이용해서 쉽게 풀 수 있는 문제이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static String ans = "No";
static int r;
static int c;
static char[][] map;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
r = Integer.parseInt(input[0]);
c = Integer.parseInt(input[1]);
map = new char[r][c];
visited = new boolean[r][c];
for(int i=0; i<r; i++) {
String row = br.readLine();
for(int j=0; j<c; j++)
map[i][j] = row.charAt(j);
}
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(ans.equals("Yes")) {
System.out.println(ans);
return;
}
if(!visited[i][j]) {
visited[i][j] = true;
dfs(i, j, map[i][j], -1);
}
}
}
System.out.println(ans);
}
public static void dfs(int x, int y, char color, int idx) {
if(ans.equals("Yes")) return;
for(int i=0; i<4; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(idx+i==1 || idx+i==5) continue;
if(nx<0 || nx>=r || ny<0 || ny>=c || map[nx][ny]!=color) continue;
if(visited[nx][ny]) {
ans = "Yes";
return;
}
visited[nx][ny] = true;
dfs(nx, ny, color, i);
}
}
}