[백준] G3 9944 NxM 보드 완주하기 (java)

www.acmicpc.net/problem/9944

9944번: NxM 보드 완주하기

 

풀이

 

1) 이 문제는 테스트케이스의 수가 정해져 있지 않다. while문으로 조건 만족시 계속 돌아가는식으로 짠다.

2) 입력값을 담을 char map[][], 방문체크용 boolean isVisited[][], 최종 결과값 min 생성

3) map에 입력값을 담음. 여기서 '.' 의 개수를 미리 points 변수에 저장

3) map을 탐색하면서 '.' 이 나오면 방향별로 한번씩 dfs를 4번 돌림. (상, 하, 좌, 우)

3-1) dfs의 파라미터는 (행, 열, 방향, 이동횟수, 이동거리) 이다.

3-2) dfs의 탈출조건은 이동거리가 points 가 되었을 경우이다. 이때 이동횟수의 min을 갱신한다

3-3) 벽, 장애물, 왔던곳을 만나기 전에는 직진해야하므로 방향을 그대로 좌표와 이동거리만 바꾸면서 탐색한다.

3-4) 벽, 장애물, 왔던곳을 만나면 이동횟수를 +1 하여 4방향으로 dfs 탐색

3-5) 백트래킹은 알아서잘하자

4) min 을 출력한다. min이 바뀌지 않았다면 전부 돌 수 없는 경우이므로 -1 출력

 

주의사항

 

1) 한칸만 뚫려있을 경우 이동횟수는 0이다 <- 개빡침

 

package com.baekJoon;

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

public class BJ_G3_9944_NxM보드완주하기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int T,N,M,points,min;
	static char map[][];
	static boolean isVisited[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		String line = null;
		int T = 1; 
		while((line = input.readLine()) != null) { // 이런 구문이 되는구나..
			tokens = new StringTokenizer(line);
			N = Integer.parseInt(tokens.nextToken());
			M = Integer.parseInt(tokens.nextToken());
			map = new char[N][M];
			isVisited = new boolean[N][M];
			min = Integer.MAX_VALUE;
			points = 0;
			
			for(int r=0; r<N; r++) {
				String ln = input.readLine();
				for(int c=0; c<M; c++) {
					map[r][c] = ln.charAt(c);
					if(map[r][c] == '.') {
						points++;
					}
				}	
			}
//			System.out.println("points : "+points);
			for(int r=0; r<N; r++) {
				for(int c=0; c<M; c++) {
					if(map[r][c] == '.') {
						for(int d=0; d<4; d++) {
							isVisited[r][c] = true;
							dfs(r,c,d,1,1);
//						System.out.println("--------------------------------------------");
							isVisited[r][c] = false;
						}
					}
				}	
			}
			
//			for(char x[] : map) {
//				System.out.println(Arrays.toString(x));
//			}
			if(points == 1) {
				System.out.println("Case "+T+": 0");
			}else {
				if(min == Integer.MAX_VALUE) {
					System.out.println("Case "+T+": -1");
				}else {
					System.out.println("Case "+T+": "+min);
				}
			}
			T++;
			
		}
	}

	private static void dfs(int r, int c, int dir, int cnt, int depth) {
		if(depth == points) {
//			System.out.println("r : "+r+",  "+"c : "+c+",  "+"dir : "+dir+",  "+"cnt : "+cnt+",  "+"depth : "+depth);
			if(min > cnt) {
				min = cnt;
			}
			return;
		}
//		System.out.println("r : "+r+",  "+"c : "+c+",  "+"dir : "+dir+",  "+"cnt : "+cnt+",  "+"depth : "+depth);
		int nr = r + dr[dir];
		int nc = c + dc[dir];
		if(isIn(nr, nc) && !isVisited[nr][nc] && map[nr][nc]=='.') {
			isVisited[nr][nc] = true;
			dfs(nr, nc, dir, cnt, depth+1);
			isVisited[nr][nc] = false;
		}else { // 꺽어야 할 때
			for(int d=0; d<4; d++) {
				int nnr = r + dr[d];
				int nnc = c + dc[d];
				if(isIn(nnr, nnc) && !isVisited[nnr][nnc] && map[nnr][nnc] == '.') {
					isVisited[nnr][nnc] = true;
					dfs(nnr, nnc, d, cnt+1, depth+1);
					isVisited[nnr][nnc] = false;
				}
			}
		}
	}
	
	static int dr[] = {-1,1,0,0}; // 상하좌우
	static int dc[] = {0,0,-1,1};
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<M);
	}
	static String src =
			"5 5\r\n" + 
			"**...\r\n" + 
			".....\r\n" + 
			"....*\r\n" + 
			"..*..\r\n" + 
			".....\r\n" + 
			"3 4\r\n" + 
			"****\r\n" + 
			"*...\r\n" + 
			"*..*";
}

 

 

후기

 

백준에서 테스트케이스의 수가 정해져 있지않은 문제를 처음 접해보았다.

구글링을 통해 라인을 String으로 미리 입력받고 while((line = input.readLine()) != null) 로 돌리는 방법이 있다는것을 알게되었다. 뭔가 색다른 입력방식이여서 당황했지만 좋은 경험이었다.

문제는 동 난이도 '수족관 1'에 비하면 쉬운 문제였지만 방향처리 때문에 많이 틀렸다.

dfs 및 백트래킹 연습에도 훌륭한 문제였다.