문제
R x C 격자에서 첫 번째 열(원재 집)에서 마지막 열(빵집)까지 파이프를 연결할 때, 서로 겹치지 않게 최대 몇 개의 파이프를 연결할 수 있는지 구하라. 이동은 오른쪽 위, 오른쪽, 오른쪽 아래 3방향만 가능하다.
입력
첫째 줄에 R, C, 이후 R줄에 격자가 주어진다 (.은 빈칸, x는 건물).
출력
연결 가능한 최대 파이프 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 5 ..... ..... ..... ..... ..... | 5 |
풀이
그리디 + DFS로 위쪽 행부터 시도하여 가능한 경로를 확정하고, 실패한 칸은 재방문하지 않는다.
- 위쪽 행부터 순서대로 첫 번째 열에서 DFS를 시작한다
- 오른쪽 위 → 오른쪽 → 오른쪽 아래 순서로 시도한다
- 마지막 열에 도달하면 성공, 방문한 칸은 '-'로 표시하여 재사용 방지
- 실패 시에도 방문 표시를 유지하여 다른 경로가 같은 칸을 탐색하지 않도록 한다
핵심 아이디어: 위쪽 행 우선으로 경로를 확보하면 아래쪽 행에 더 많은 공간을 남기므로 그리디가 최적이다.
코드
package day649;
import java.io.*;
import java.util.*;
public class Day626BOJ3109빵집 {
static int R, C, val;
static char[][] map;
public static void main(String[] args) throws Exception {
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++)
map[i] = br.readLine().toCharArray();
for (int i = 0; i < R; i++)
if (check(i, 0))
val++;
System.out.println(val);
}
public static boolean check(int x, int y) {
map[x][y] = '-';
if (y == C - 1)
return true;
if (x > 0 && map[x - 1][y + 1] == '.')
if (check(x - 1, y + 1))
return true;
if (map[x][y + 1] == '.')
if (check(x, y + 1))
return true;
if (x + 1 < R && map[x + 1][y + 1] == '.')
if (check(x + 1, y + 1))
return true;
return false;
}
}복잡도
- 시간: O(R * C)
- 공간: O(R * C)