[백준/DFS, 백트래킹] 3190 : 빵집 - 자바

문제

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

3109번: 빵집

 

풀이

좌측 열에서부터 우측 열까지 놓을 수 있는 파이프의 최대 갯수를 구하여야 한다.

DFS를 사용하여 한칸씩 우측열로 이동할 때마다 우측 상단, 우측, 우측 하단 순으로 파이프를 놓을 수 있는지 없는지 탐색하였다.

좌측 열 처음부터 우측 열 끝까지 도달하면 파이프를 놓을 수 있는 갯수를 추가하였는데 

이 때 파이프가 우측 열 끝가지 도달하던(경로탐색 성공), 도달하지 않던(경로탐색 실패) 이전에 탐색한 경로를 탐색했다는 것을 맵에 남겨두는 것이 포인트인다.

 

탐색했다는 것을 남겨두지 않으면 우측상단, 우측, 우측하단 3가지 경우의 수를 탐색하면서 C(열크기) 만큼 반복하여야 하기 때문에 이미 탐색한 경로를 체크하는 것이 중요하다.

이를 체크하지 않으면 최악의 경우 3^C X R 경우의 수만큼 반복한다.

(예제에서 R=5,C=5 지만 R=10000, C=500이라면 시간초과가 당연히 발생한다.)

 

작성한 코드는 다음과 같다. 

package BOJ.BFSDFS;

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

public class BOJ_3109 {
	static char[][] map;
	static int R, C;
	// 우상, 우, 우하
	static int[] dr = {-1,0,1};
	static int[] dc = {1,1,1};
	
	public static void main(String[] args) throws IOException {
		int cnt = 0;
		input(); // 입력
		
		// 로직
		for (int r = 0; r < R; r++) {
			if(DFS(r,0)) cnt++;
		}
		System.out.println(cnt);		
	}
	
	public static boolean DFS(int r, int c) {
		map[r][c] = 'P';
		if(c == C-1) return true; // 마지막 열에 도착하면 true반환
		
		for (int d = 0; d < 3; d++) { //우상, 우, 우하 탐색
			int nr = r + dr[d];
			int nc = c + dc[d];
			if((nr >= 0 && nr < R) && map[nr][nc] == '.') { // 맵 범위 안에 있고, 건물이 없다면
				if(DFS(nr, nc)) return true;
			}
		}
		return false;
	}
	
	public static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new char[R][C];
		
		for (int i = 0; i < R; i++) {
			String input = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = input.charAt(j);
			}
		}
	}
}

 

여기서 우측으로 계속 탐색하기 때문에 delta를 활용하여 nc 부분은 for문을 돌리지 않고 +1 하면 코드는 더욱 간결해질 것이다. 

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

public class BOJ_3109_Sol2 {
	static char[][] map;
	static int ans, R, C;
	static StringTokenizer st;
	static int[] dr = {-1,0,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][]; //행만 크기를 잡아놓고 한줄 한줄 받아서 배열로 넣을 것임.
		
		for (int i = 0; i < R; i++) map[i] = br.readLine().toCharArray();
		for (int i = 0; i < R; i++) DFS(i, 0);
		
		System.out.println(ans);
	}

	public static boolean DFS(int r, int c) {
		map[r][c] = 'x';
//		map[r][c] = '.'; // 실패한 경우도 다시 탐색하게 됨.
		if(c == C-1) {
			++ans;
			return true;
		}
		
		int nr, nc = c + 1;
		
		for (int d = 0; d < 3; d++) {
			nr = r + dr[d];
			if(nr < 0 || nr >= R || map[nr][nc] == 'x') continue;
			if (DFS(nr, nc)) return true;
		}
		
		return false;
	}
}