[BOJ/Java] 3109. 빵집

[BOJ/Java] 3109. 빵집

3109번: 빵집

---

문제 해석

이 문제에서는 빵집을 기점으로 여러 파이프라인을 연결하여 최대한 많은 가정에 도달하는 것이 목표다. 파이프라인은 상단, 중앙, 하단 방향으로 연결할 수 있으며, 연결 과정에서 장애물을 피해야 한다. 이 문제는 가능한 많은 파이프라인을 설치하는 최적의 방법을 찾는 것을 요구한다.

풀이 과정

제출된 Java 코드는 깊이 우선 탐색(DFS)를 활용하여 각 가능한 경로를 탐색하고, 파이프라인을 설치한다. 이 탐색은 모든 가능한 경로를 고려하며, 성공적으로 도착점에 도달할 때까지 계속된다.

 

• 데이터 입력: 빵집의 지도 크기와 각 위치의 상태('.'는 빈 공간, 'x'는 장애물)를 입력받는다.
• DFS 구현: 각 행에서 시작하여 가능한 모든 경로를 탐색한다. 이 때, 재귀적으로 다음 칸을 탐색하며, 가능한 경로를 찾는다.
• 파이프라인 설치: 각 경로가 성공적으로 마지막 열에 도달하면, 해당 경로는 파이프라인으로 확정되며, 추가적인 경로 탐색을 중지한다.

코드

package edu.ssafy.im.BOJ.Gold.G2.No3109;

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

public class Main {
	private int r, c, ans = 0;
	private boolean[][] graph; // 그래프의 접근 가능 여부를 저장하는 배열
	private int[] direction = { -1, 0, 1 }; // 탐색할 수 있는 세 가지 방향 (위, 중간, 아래)
	
	public static void main(String[] args) throws IOException {
		new Main().sol();
	}

	private void sol() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken()); // 행의 수
		c = Integer.parseInt(st.nextToken()); // 열의 수
		graph = new boolean[r][c]; // 그래프 초기화
		
		for (int i = 0; i < r; i++) {
			String string = br.readLine(); // 각 행의 입력 받기
			for (int j = 0; j < c; j++) {
				if (string.charAt(j) == '.') {
					graph[i][j] = true; // 접근 가능
				} else {
					graph[i][j] = false; // 장애물
				}
			}
		}

		for (int i = 0; i < r; i++) {
			dfs(i, 0); // 각 행에서 시작하는 DFS 탐색
		}

		sb.append(ans); // 최종 결과 (설치 가능한 최대 파이프라인 수)
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private boolean dfs(int x, int y) {
		if (y == c - 1) { // 마지막 열에 도달했다면
			ans++; // 파이프라인 설치 완료
			return true;
		}

		graph[x][y] = false; // 현재 위치를 방문 처리

		for (int d = 0; d < direction.length; d++) { // 가능한 모든 방향으로 탐색
			int nx = x + direction[d];
			int ny = y + 1;
			if (0 <= nx && nx < r && 0 <= ny && ny < c && graph[nx][ny]) {
				if (dfs(nx, ny)) {
					return true; // 성공적으로 도달한 경우, 추가 탐색 중지
				}
			}
		}

		return false; // 해당 경로에서는 도달할 수 없음
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 각 셀에 대한 DFS 호출을 포함하므로 최악의 경우 O(R×C)가 될 수 있다. 그러나 경로를 성공적으로 찾은 후에는 더 이상의 탐색을 중단하기 때문에, 실제 시간 복잡도는 이보다 효율적일 수 있다.

느낀점

이 문제를 통해 그래프 탐색을 이용하여 실제로 적용 가능한 최적화 문제를 해결하는 방법을 경험할 수 있었다. 파이프라인 설치 문제는 실생활에서의 다양한 최적화 문제와 유사하여, 이러한 문제 해결 기술은 다른 많은 분야에서도 응용될 수 있다.

.