2178번 / 미로 탐색 / DFS

[ZZANZU]

https://www.acmicpc.net/problem/2178

우선은 DFS로 풀어봄.

	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
...
		// 2. 연결된 길을 찾는다.(상하좌우, 4가지) dx, dy를 사용하는 것에 집중!
		for(int i = 0; i < 4; i++) {
			int targetX = x + dx[i];
			int targetY = y + dy[i];
			

• 한 위치에서 상,하,좌,우를 탐색하기 위해 현재 위치 (x, y)에 미리 정의한 탐색 좌표 이동거리 dx, dy를 정의해서 for문안에서 탐색

• 채점 상으로는 시간 초과

기존 코드

package example02;

import java.util.Arrays;
import java.util.Scanner;

public class Problem2178 {
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		
		// 그래프의 노드의 번호가 1,2,3 이런게 아니라서 그냥 N,M 써줌
		map = new int[N][M];
		visited = new boolean[N][M];
		
		// 여기서 int로 String의 한 글자를 받아보는 방식 ㅇㅇ
		for(int y = 0; y < N; y++) {
			String temp = sc.nextLine();
			
			for(int x = 0; x < M; x++) {
				if(temp.charAt(x) == '1') {
					map[y][x] = 1;
				} else {
					map[y][x] = 0;
				}
			}
		}
		
		dfs(0, 0, 1);
		System.out.println(min);
	}
	
	public static void dfs(int x, int y, int current) {
		// 0. 목적지 도달 여부 체크 , 이 부분을 생각 못함!
		if(y == N-1 && x == M-1) {
			if(current < min) {
				min = current;
			}
			return; // 쓸데없는 길 탐색 안하게 해줌
		}
		// 1. 방문 기록을 남긴다.
		visited[y][x] = true;
		
		// 2. 연결된 길을 찾는다.(상하좌우, 4가지) dx, dy를 사용하는 것에 집중!
		for(int i = 0; i < 4; i++) {
			int targetX = x + dx[i];
			int targetY = y + dy[i];
			
			if(targetX >= 0 && targetX < M && targetY >= 0 && targetY < N) {
				// 3. 갈 수 있는 길을 찾는다.
				if(map[targetY][targetX] == 1 && visited[targetY][targetX] == false){
					// 4. 간다
					dfs(targetX, targetY, current+1);
				}				
			}
		}
		// 5. 방문 해지
		visited[y][x] = false;
	}

}

근데 여기서 visited를 int형으로 바꿔서 각 칸이 방문이 되었을 때 거기를 지나간 당시의 거리(current)를 저장하게 된다. 그러면 다음번에 그 칸을 지나가게 되었을 때의 current와 visited(이전의 방문시 거리)를 비교한다.

public static void dfs(int x, int y, int current) {
		// 0. 목적지 도달 여부 체크 , 이 부분을 생각 못함!
		if(y == N-1 && x == M-1) {
			if(current < min) {
				min = current;
			}
			return; // 쓸데없는 길 탐색 안하게 해줌
		}
		// 1. 방문 기록을 남긴다.
		visited[y][x] = current;
		
		// 2. 연결된 길을 찾는다.(상하좌우, 4가지) dx, dy를 사용하는 것에 집중!
		for(int i = 0; i < 4; i++) {
			int targetX = x + dx[i];
			int targetY = y + dy[i];
			
			if(targetX >= 0 && targetX < M && targetY >= 0 && targetY < N) {
				// 3. 갈 수 있는 길을 찾는다.
				if(map[targetY][targetX] == 1){
					if(visited[targetY][targetX] == 0 || visited[targetY][targetX] > current+1)
					// 4. 간다
					dfs(targetX, targetY, current+1);
				}				
			}
		}
		// 5. 방문 해지
//		visited[y][x] = 0;
	}

• '1. 방문 기록을 남긴다' 단계에서 방문 여부를 저장하는 것이 아니라, 해당 위치까지의 거리를 저장한다
  그렇게 되면 다음번에 해당 위치를 다시 한 번 방문하게 되었을 때, 이 값(visited)을 current와 비교하여 탐색을 더 할지 결정하게 된다.

• 방문 해지는 하지 않는다!