[JAVA] 백준 3109 : 빵집

문제

3109번: 빵집

해결 방법

처음엔 BFS 로 탐색을 시도했었는데 문제가 파이프를 생성하고 그 파이프가 지나간 길을 제외한 다른 길에 새로운 파이프를 연결하는 방식이라 DFS로 시작점부터 끝점까지 한 번에 파악하는게 DFS가 맞는 것 같아서 수정해서 풀었다.

 

처음 생각했던 것은 파이프가 이어지는 방식이다.

문제에서 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로만 이동이 가능하다고 했는데, 왼쪽 제일 윗 칸인 (0, 0)에서 부터 탐색을 시작하는 점을 감안하여 보면 오른쪽 위, 오른쪽, 오른쪽 아래 순서로 탐색을 해야 그 다음 탐색할 부분과의 간섭이 적은 지점으로 탐색이 가능하다고 생각하여 위와 같은 순서대로 탐색하게끔 코드를 구성하였다.

 

그리고 여기서 가장 중요한 것은 끝점까지 탐색을 완료하였을 때 현재 진행 중인 파이프의 재귀를 모두 다 종료를 해줘야한다는 것인데, 이 부분 때문에 다른 블로그를 참고하여 코드를 완성하였다.

참고한 블로그 : machine-geon.tistory.com/131

 

재귀를 왜 종료해주어야 하는지 예시 입력을 바탕으로 (0, 0)에서 시작하는 DFS 탐색을 예로 들어보겠다.

(0, 0)에서 시작한 탐색은 (1, 1) -> (2, 2) -> (1, 3) -> (0, 4) 의 순서로 탐색을 완료한다.

(0, 4)라는 목적지에 도착하였지만 아직 (2, 2)에서 (1, 3)이 아닌 (2, 3)으로 이동이 가능한 재귀가 존재하고 그 곳으로도 이동하려고 할 것이다. 그렇기 때문에 목적지에 도착한 파이프의 남은 재귀들은 추가적으로 탐색을 하지 못하게끔 boolean 변수를 추가해서 목적지에 도달한 재귀의 모두를 추가 탐색없이 종료시켜 주었다.

 

그리고 방문 확인은 굳이 visit 배열을 사용하지않고 map 자체를 'x'로 바꿔주는 등 다른 좋은 방법들도 존재한다.

나머지는 코드를 참고하면 될 것 같다.

 

코드

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

public class Main {
	static int dx[] = {-1, 0, 1}; // 우측 위, 우측, 우측 아래 순서로 탐색
	static int dy[] = {1, 1, 1};
	
	static int R, C;
	static char[][] map;
	static boolean[][] visit;
	
	static int cnt;
	static boolean check;

	public static void main(String[] args) 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];
		visit = new boolean[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);
			}
		}
		
		for (int i = 0; i < R; i++) {
			check = false; // 새로 탐색을 하기 때문에 false로 변경
			dfs(new Node(i, 0));
		}
		System.out.println(cnt);
	}
	
	static void dfs(Node node) {
		if (node.y == C - 1) {
			check = true;
			cnt++;
			return;
			// 최종 목적지에 도달하였기 때문에 check를 true로.
		}
		
		visit[node.x][node.y] = true;
		
		for (int j = 0; j < 3; j++) {
			int newX = node.x + dx[j];
			int newY = node.y + dy[j];
			
			if (newX >= 0 && newY >= 0 && newX < R && newY < C && map[newX][newY] == '.' && !visit[newX][newY]) {
				if (check) return;
				// 탐색이 이미 목적지에 갔다면 나머지 재귀들이 추가탐색을
				// 하지 않도록 종료 시킨다.
				dfs(new Node(newX, newY));
			}
		}
	}
}

class Node {
	int x;
	int y;
	
	Node (int x, int y) {
		this.x = x;
		this.y = y;
	}
}