체크 포인트
1. DFS(깊이 우선 탐색)을 이용하는 문제
-출발지에서 도착지까지 갈 수 있는 '모든 경우의 수'를 탐색하는 문제
2. 도착지까지 방문 후 또 다른 경로로의 탐색을 이어가게 하는 것
// 새로운 nx, ny가 지도 배열 내 위치하고,
if(nx>=1 && ny>=1 && nx<8 && ny<8) {
// 해당 위치가 섬이고, 방문한 적이 없다면,
if(map[nx][ny]==0 && !visited[nx][ny]) {
// 현재 위치 방문 처리
visited[x][y] = true;
// 새로운 DFS탐색 시작
DFS(nx,ny);
// 다른 경로 재탐색을 위한 false 처리
visited[x][y] = false;
}
}
- 새로운 DFS(nx,ny)를 탐색하기 전에 (x,y)를 방문처리(visited[x][y]=true) 후,
- 새로운 DFS(nx,ny)의 탐색이 끝나면 또 다른 경로 탐색을 처리하기 위해 visited[x][y] = false 처리를 하는 것이 포인트
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 육지와 바다를 표시해주는 지도 배열
static int[][] map;
// 해당 위치에 방문여부를 담는 배열
static boolean[][] visited;
// 상,하,좌,우 탐색을 위한 x,y
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};
// 섬 개수 카운트 변수
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// 지도 배열 초기화
map = new int [8][8];
// 방문 배열 초기화
visited = new boolean[8][8];
// 지도 내 섬의 값 입력
for(int i=1; i<8; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j=1; j<8; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 지도 내 입력값 확인
/*
for(int i=1; i<8; i++) {
for(int j=1; j<8; j++) {
if(j==7) {
System.out.println(map[i][j] + " ");
}
else {
System.out.print(map[i][j] + " ");
}
}
}
*/
// DFS 탐색 시작 부분
DFS(1,1);
// DFS 탐색이 끝난 후 총 count 출력
System.out.println(count);
}
static void DFS(int x, int y) {
// 도착지에 도착했을 때,
if(x==7 && y==7) {
// 미로탈출 경로의 개수 추가
count++;
// 다른 경로가 있는지 탐색하기 위해 return;
return;
}
// 상,하,좌,우,대각선 탐색 시작
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 새로운 nx, ny가 지도 배열 내 위치하고,
if(nx>=1 && ny>=1 && nx<8 && ny<8) {
// 해당 위치가 섬이고, 방문한 적이 없다면,
if(map[nx][ny]==0 && !visited[nx][ny]) {
// 현재 위치 방문 처리
visited[x][y] = true;
// 새로운 DFS탐색 시작
DFS(nx,ny);
// 다른 경로 재탐색을 위한 false 처리
visited[x][y] = false;
}
}
}
}
} // end of Main
'코딩테스트' 카테고리의 다른 글
[인프런 자바/java] 3. 최대점수 구하기(DFS) _디버깅의 눈물 (0) | 2022.09.13 |
---|---|
[인프런 자바/java] 2. 바둑이 승차(DFS) _디버깅의 눈물 (0) | 2022.09.12 |
[인프런 자바/java] 13. 섬나라 아일랜드 _디버깅의 눈물 (1) | 2022.09.10 |
[인프런 자바/java] 12. 토마토(BFS 활용) _디버깅의 눈물 (3) | 2022.09.08 |
[인프런 자바/java] 11. 미로의 최단거리 통로(BFS) _디버깅의 눈물 (0) | 2022.09.08 |