반응형
11-22 12:55
- Today
- Total
Link
개발하는 고라니
[백준] 16929번 : Two Dots 본문
반응형
[DFS]
DFS를 이용해 A ~ Z로 이루어진 격자에서 사이클이 존재하는지 여부만 판단하면 된다.
사이클을 확인하는 알고리즘은 다음과 같이 작성했다.
static boolean visit = new boolean[51][51];
static boolean cycle;
/*
현재 방문하고 있는 정점이 이미 방문되었고, cnt가 4이상이면 cycle을 찾았다고 판단
*/
static void DFS(int y, int x, int bY, int bX, int cnt){
//현재 정점이 이미 방문한 곳 & 4개 이상을 거쳤는지?
if(visit[y][x] && cnt >= 4){
cycle = true;
return;
}
visit[y][x] = true;
char cur = map[y][x];
for(int a=0; a<4; a++){
int ny = y+Y[a];
int nx = x+X[a];
//범위를 넘지않고, 현재 정점의 알파벳과 동일한지? 바로 다음 정점이 이전 정점과 다른지?
if(ny < 1 || nx < 1 || ny > n || nx > m || map[ny][nx] != cur) continue;
if(ny == bY && nx == bX) continue;
DFS(ny, nx, y, x, cnt + 1);
}
}
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
static char[][] map = new char[51][51];
static boolean[][] visit = new boolean[51][51];
static boolean cycle;
static void DFS(int y, int x, int bY, int bX, int cnt){
if(visit[y][x] && cnt >= 4){
//System.out.println("(" + y+", " + x +") 에서 사이클 발생");
cycle = true;
return;
}
visit[y][x] = true;
char cur = map[y][x];
for(int a=0; a<4; a++){
int ny = y+Y[a];
int nx = x+X[a];
if(ny < 1 || nx < 1 || ny > n || nx > m || map[ny][nx] != cur) continue;
if(ny == bY && nx == bX) continue;
DFS(ny, nx, y, x, cnt + 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());
for(int i=1; i<=n; i++){
char[] str = br.readLine().toCharArray();
for(int j=1; j<=m; j++)
map[i][j] = str[j-1];
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
if(!visit[i][j])
DFS(i, j, 0, 0, 1);
}
System.out.println(cycle? "Yes":"No");
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 14950번 : 정복자 (0) | 2021.05.02 |
---|---|
[백준] 2562번 : 최댓값 (0) | 2021.05.01 |
[백준] 1938번 : 통나무 옮기기 (0) | 2021.04.30 |
[백준] 11021번 : A + B - 7 (0) | 2021.04.28 |
[백준] 16932번 : 모양 만들기 (0) | 2021.04.15 |
Comments