백준 9944 - NxM 보드 완주하기 (Java)

www.acmicpc.net/problem/9944

9944번: NxM 보드 완주하기

 

1. 유형

구현, 백트래킹, dfs

 

2. 자료구조

- 딱히 없음

 

3. 기능

- EOF로 입력받기

- 처음 구슬 시작점 설정

- 벽 만날때 까지 이동

• 벽 만난 경우
  • 제자리에서 벽 부딪힌 경우
  • 이동하다가 벽 부딪힌 경우

- 재귀를 나와서 방문배열 복구

 

4. 풀이

 

구슬 시작점은 2중 탐색으로 벽이 아닌 위치에서 시작

4방향 탐색하면서 while문을 돌려서 벽인경우, 맵 이탈하는 경우, 중복하는 경우에서 반복문 탈출

만약, 한발자국도 못가고 벽을 만나면 방향을 바꿔줌.

이동하다가 벽 만나면 재귀를 돌려서 다시 그 자리부터 시작

 

난 방문배열을 복사해서 사용했지만 시간초과가 나왔다. 따라서 한 배열을 가지고

재귀마다 사용해줘야 한다. 따라서 재귀를 나오고 재활용하기 위해 구슬이 이동하기 전으로 복구 해줘야함.

 

코드.

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

public class Main {
	static int N, M, dotNum, min;
	static char map[][];
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int tc = 1;
		String input="";
		while ((input = in.readLine() )!= null) {
			st = new StringTokenizer(input);
			N = Integer.valueOf(st.nextToken());
			M = Integer.valueOf(st.nextToken());
			map = new char[N][M];
			dotNum = 0;
			min = Integer.MAX_VALUE;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine());
				String tmp = st.nextToken();
				for (int j = 0; j < M; j++) {
					map[i][j] = tmp.charAt(j);
					if (map[i][j] == '.') {
						dotNum++;
					}
				}
			}
			// dfs
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] != '*') {
						boolean visit[][] = new boolean[N][M];
						visit[i][j] = true;
						dfs(i, j, visit, 1, 0);
						visit[i][j] = false;
					}
				}
			}
			if (min == Integer.MAX_VALUE) {
				System.out.println("Case " + String.valueOf(tc) + ": -1");
			} else {
				System.out.println("Case " + String.valueOf(tc) + ": " + min);
			}
			tc++;
		}
	}

	static void dfs(int r, int c, boolean visit[][], int dot, int edge) {
		if (dot == dotNum) {
			min = Math.min(min, edge);
			return;
		}
		for (int k = 0; k < 4; k++) {
			int cnt = 0;
			int cr = r;
			int cc = c;
			// 깊은 복사
			while (true) {
				int nr = cr + dr[k];
				int nc = cc + dc[k];

				// 이탈하는 경우
				if (nr < 0 || nr >= N || nc < 0 || nc >= M || visit[nr][nc] || map[nr][nc] == '*') {
					break;
				}
				cr = nr;
				cc = nc;
				visit[nr][nc] = true;
				cnt++;
			}
			if (r == cr && c == cc) {
				continue;
			} else {
				dfs(cr, cc, visit, dot + cnt, edge + 1);
				
				for (int d = 1; d <= cnt; d++) {
					int y = r + dr[k] * d;
					int x = c + dc[k] * d;
					visit[y][x] = false;
				}
			}
		}
	}
}

5. 느낀점

EOF에 대해서 알 수 있었다.