[백준 / Java] 3109번: 빵집 (골드2)

문제 풀이 날짜: 2023.08.16
포스트 작성일: 2023.08.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 3109번: 빵집 (골드2)

 

키워드

그리디, DFS (그래프), 백트랙킹

 

풀이 접근법

• 가능한 공간내에 파이프를 많이 설치해야하기 때문에 0번째 행부터 탐색한다. (그리디)
• 탐색 순서는 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 한다.
• 그리디하게 접근해도 되는 문제이기 때문에, 이미 하나의 파이프를 설치했다면 그 외의 경우를 고려하지 않고 가지치기 해야 한다. ( if(finished) continue; )
  • 즉, 유망하지 않은 길이 있다면 자식노드의 탐색을 중단하고 다른 경우를 탐색한다.
  • 이 문제의 경우 1. 길이 막혀있을 경우 2. 이미 완성된 루트를 지나가려고 하는 경우의 두 가지를 유망하지 않은 것으로 본다.

 

코드

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

public class Main {

	private static int R;
	private static int C;
	
	private static int answer = 0;
	private static boolean finished;
	
	private static final char BUILDING = 'x';
	private static final char ROAD = '.';
	
	private static int[] dy = {-1, 0, 1};
	private static int[] dx = {1, 1, 1};
	
	private static char[][] map;
	private static boolean[][] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input = br.readLine().split(" ");
		
		R = Integer.parseInt(input[0]);
		C = Integer.parseInt(input[1]);
		
		map = new char[R][C];
		visited = new boolean[R][C];
		
		for(int i = 0; i < R; i++) {
			String line = br.readLine();
			for(int j = 0; j < C; j++) {
				map[i][j] = line.charAt(j);
			}
		}
		
		for(int i = 0; i < R; i++) {
			finished = false; //새 루트를 찾을 때 초기화
			DFS(i, 0);
		}

		System.out.println(answer);
	}
	
	public static void DFS(int row, int col) {
		if(col == C - 1) {
			answer++;
			finished = true; //한 루트를 발견했으므로 체크
			return;
		}
		
		for(int i = 0; i < dy.length; i++) {
			int nr = row + dy[i];
			int nc = col + dx[i];
			
			if(!isValid(nr, nc)) {
				continue;
			}
			
			if(map[nr][nc] == BUILDING) {
				continue;
			}
			
			if(visited[nr][nc]) {
				continue;
			}
			
			if(finished) continue; //이미 최적 경로를 찾았다면 중단
			
			visited[nr][nc] = true;
			DFS(nr, nc);
		}
		
		return;
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < R && nc < C);
	}

}

---

이미 최적의 경로를 찾았다면 자식노드를 탐색하지 않고 반환해주는 것이 아주 중요한 문제였다. 그 부분을 빠트려서 제대로 된 답을 내지 못했었다. 백트랙킹의 본질을 다시 공부할 필요가 있겠다.  

 

참고한 링크

https://velog.io/@qwerty1434/백준-3109번-빵집

 

git 링크

(git 링크 첨부)