https://www.acmicpc.net/problem/16929
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static char[][] arr;
static boolean[][] visit;
static int n, m;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int startX, startY;
public static void dfs(int x, int y, char color, int cnt) {
if (cnt >= 4 && x == startX && y == startY) { // 변이 네개 이상이고 처음 위치와 동일하다면
System.out.println("Yes");
System.exit(0);
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || visit[nx][ny] || color != arr[nx][ny]) continue;
visit[nx][ny] = true;
dfs(nx, ny, color, cnt + 1);
visit[nx][ny] = false;
}
}
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());
arr = new char[n][m];
visit = new boolean[n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
arr[i][j] = str.charAt(j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
startX = i;
startY = j;
char color = arr[i][j];
dfs(i, j, color, 1);
}
}
System.out.println("No");
}
}
dfs로 같은 색상일 경우 탐색해 나가다가 시작점으로 다시 돌아오면 사이클이다.
이 때 사이클일 때 변의 개수가 무조건 4이상이여야 하므로 카운트가 4이상인지 체크해줘야한다. 이걸 안해서 좀 헤맸다ㅠㅠ
'ALGORITHM' 카테고리의 다른 글
[JAVA] 프로그래머스 - 숫자 문자열과 영단어 (0) | 2022.12.19 |
---|---|
[JAVA] 알고리즘 : 단어 뒤집기 (0) | 2022.12.19 |
[JAVA] 백준 1182 - 부분수열의 합 (0) | 2022.12.17 |
[JAVA] 백준 13023번- ABCDE (0) | 2022.12.17 |
[JAVA] 백준 7576번- 토마토 (0) | 2022.12.16 |