BOJ - 3109 빵집

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

---

Problem

---

Solve

주어진 조건

• 파이프는 첫번째 열(가스관)에서 부터 마지막 열(빵집)까지 연결되어야한다.
• 파이프는 건물이 있는 곳과 파이프가 존재하는 곳에는 설치할수 없다.
• 파이프는 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선 3방향으로만 설치할수 있다.

문제를 보고 파이프를 첫번째 열의 첫번째 행부터 R번째 행까지 순서대로 돌면서 파이프를 최대한 위쪽(오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선 순)을 향해 설치하면 파이프를 최대한 많이 설치할수 있을것 같다는 생각을 했다.

하지만 시간초과가 발생했고 질문게시판에서 답을 찾게 되었다.

출발하는 파이프에서 3가지 방향을 탐색하며 마지막 열까지 이동하게 되면 O(3^500)의 시간복잡도가 발생하게 되고 모든 행을 탐색하게 되면 O(10000 * 3^500)으로 시간초과가 발생할수밖에 없었다.

해당 문제를 해결하기 위해서 파이프를 연결하는 DFS에서 백트래킹을 제거했다.
이말인 즉슨 한번 방문했던 곳은 방문하지 않는다는 뜻이다.
왜냐하면 map[i][j]를 통해 파이프를 연결했거나 연결하지 못했거나 이 좌표에 접근해서 파이프를 연결해봤자 결과는 동일하기 때문이다.(이 좌표를 통해 파이프 연결이 성공했다면 다른 파이프는 더 이상 설치할수없는것이고 파이프 연결이 실패했다면 이쪽을 향해 설치한다면 실패할수 밖에 없다는 것이다.)

풀이 순서는 아래와 같다.

1. 첫번째 행부터 마지막 행까지 파이프를 마지막 열로 연결함수 호출.

• 각 행을 첫번째 열부터 오른쪽 위로 대각선, 오른쪽, 오른쪽 아래 대각선 순서대로 DFS를 하여 마지막 열까지 이동한다.
• 연결한 파이프의 좌표에는 visit여부를 체크하여 다른 파이프의 접근을 막는다.

2. 파이프 연결함수에서 파이프 연결이 성공하면 파이프 연결 개수를 +1한다.
3. 모든 행을 돌았다면 저장된 파이프 연결 개수를 반환한다.

---

Code

public class 빵집 {
	static int R;
	static int C;
	static String[][] map;
	static boolean[][] visit;

	//순서대로 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선
	static int[] dy = {-1, 0, 1};
	static int[] dx = {1, 1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		map = new String[R][C];
		visit = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			// st = new StringTokenizer(br.readLine());
			String[] row = br.readLine().split("");
			for (int j = 0; j < C; j++) {
				map[i][j] = row[j];
			}
		}

		int count = 0;

		for (int r = 0; r < R; r++) {
			if (dfs(r, 0)) {
				count++;
			}
		}

		bw.write(String.valueOf(count));
		bw.flush();
		bw.close();
	}

	//파이프 연결
	static boolean dfs(int r, int c) {
    	//파이프를 마지막 열(빵집)까지 연결되었다면 true반환.
		if (c == C - 1) {
			return true;
		}
		visit[r][c] = true;

		for (int d = 0; d < 3; d++) {
			int ny = r + dy[d];
			int nx = c + dx[d];

			if (ny >= 0 && nx >= 0 && ny < R && nx < C && !visit[ny][nx] && !map[ny][nx].equals("x")) {
            	//이동하려는 좌표에 건물이나 파이프가 없고 방문한 적이 없는 좌표인 경우 dfs
				if(dfs(ny, nx)){
					return true;
				}
                //백트래킹 제거
                //visit[r][c] = false;
			}
		}
		return false;
	}
}

---

Result

---

Reference

https://www.acmicpc.net/board/view/19046