본문 바로가기

코딩테스트

[인프런 자바/java] 10. 미로탐색(DFS) _디버깅의 눈물

 

 

체크 포인트

 

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