BOJ2178 미로탐색

<Solution>

1. 예전에 BFS로 풀었던 적이 있어서 DFS로 풀어보려고 했지만 흠 최단거리라서 BFS로 풀어야 되는걸까??

2. DFS돌면서 visit 체크 해주고 인접한 4방향 보면서 N M까지 찾도록 함

3. map에 cnt 값 업데이트 해주면서 진행하고 마지막에 map[N][M]에 있는 값 출력

---

<Source Code>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2178_미로탐색 {
	
	static int N;
	static int M;
	static int[][] map;
	static int[][] visit;

	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());
		map = new int[N][M];
		visit = new int[N][M];
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		int cnt = 0;
		dfs(0,0,cnt);
		System.out.println(map[N-1][M-1]);
	}
	
	static int[] dr = {0,1,0,-1};
	static int[] dc = {-1,0,1,0};
	
	public static void dfs(int i, int j, int cnt) {
		visit[i][j] = 1;
		cnt++;
		map[i][j] = cnt;
		for(int dd = 0; dd < 4; dd++) {
			int nr = i + dr[dd];
			int nc = j + dc[dd];
			if(nr < N && nc < M && nr >= 0 && nc >= 0) {
				if(map[nr][nc] != 1 || visit[nr][nc] == 1)
					continue;
				dfs(nr,nc,cnt);
				cnt--;
			}
		}
	}

}

 

---

<문제점>

1. 두번째 예시에서 9가 아니고 10이 나옴

2. dfs다시 돌아오는 경우(깊이 있게 가다가 다시 오는 경우) cnt로 되돌려주고 했는데 왜 안될까