문제 요약
빵집?
가스관 훔치기아닌가?ㅋㅅㅋ
문제에서의 이동은 항상 첫번째열에서 출발해서 마지막 열로 이동한다.
즉, 우상 대각선, 오른쪽, 우하 대각선으로만 이동한다.
또한 가스관은 서로 겹칠 수 없다. 각 칸을 지나는 파이프는 하나이어야 한다.
입/출력
입력
지도의 크기 R과 C
빵집 근처의 모습이 ‘.’과 ‘x’로 나타난다.
‘.’은 지나갈 수 있는 곳, ‘x’는 건너갈 수 없는 곳이다.
처음과 마지막열은 항상 모두 ‘.’이다.
출력
첫째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력한다.
입력 제한 크기
배열의 크기가 최대 10000*500 = 5,000,000
접근 아이디어
- 출발하는 첫 번째 열의 제일 위의 행에서부터 마지막 행까지 순서대로 마지막 열까지 도달할 수 있는지 dfs를 통해서 체크한다.
- 이 때 탐색 순서가 중요한데, 항상 우상 대각선, 오른쪽 , 우하 대각선의 순으로 체크해야한다.
- WHY? 제일 위의 행부터 탐색을 하는데, 위에서 출발한 파이프라인이 필드를 가로질러버리면 아래쪽에서는 아예 마지막 열까지 접근을 할 수가 없다.(파이프라인이 서로 겹칠 수 없기 때문)
- 또한 이미 지나간 길은 아래쪽에서 출발할 때도 마찬가지로 다시 지나갈 필요가 없다.
- 어짜피 글로 가면 시간낭비임…
- 즉 dfs에서 visited를 체크를 하고 그걸 푸는 작업을 할 필요가 없다는 것이다.
- → 만약 visited 체크를 하고 푸는 작업을 했으면 시간 초과가 났을 것…
- 이미 끝까지 도착했다면 다음 방향을 볼 필요가 없음.
- 우상 대각선, 오른쪽, 우하 대각선을 순서로 보는데, 오른쪽 하단 대각선을 선택하게 되는 경우는 아래쪽 행에서 출발하는 파이프 라인에 방해가 됨. 그래서 우하 대각선이 최선의 경우가 되는 상황은 없음.
- 즉 끝까지 도착했다면 더 이상 해당 행에 대해서는 탐색을 진행하지 않고 dfs를 종료 해야 한다.
시간 복잡도
O(R*C)가 최악이지 않나…
구현 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class B3109_빵집_조다민 {
static int R, C, cnt;
static char[][] field;
static int[] direction = {-1, 0, 1};
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());
field = new char[R][C];
for(int i = 0; i<R; i++) {
field[i] = br.readLine().toCharArray();
}
cnt = 0;
//모든 행에 대해서 탐색을 진행한다.
for(int i = 0; i<R; i++) {
dfs(i, 0);
}
System.out.println(cnt);
}
static boolean dfs(int r, int c) {
//제일 끝 행에 도달한 경우
if(c == C-1) {
cnt++;
return true;
}
int nr, nc;
for(int i = 0; i<3; i++) {
nr = r+direction[i];
nc = c+1;
//범위 밖이거나, 이미 방문했거나, 건물이거나 -> 다음 방향 보자
if(nr < 0 || nr>= R || nc <0 || nc>=C || field[nr][nc] != '.') {
continue;
}
//파이프 체크하고
field[nr][nc] = '-';
//dfs로 다음 위치를 계속해서 탐색
if(dfs(nr, nc)) { //만약 제일 끝 열에 도달했다면
return true;
}
}
return false;
}
}
'알고리즘' 카테고리의 다른 글
[BOJ2342/Java] Dance Dance Revolution (0) | 2023.08.31 |
---|---|
[BOJ20056/Java] 마법사 상어와 파이어볼 (0) | 2023.08.30 |
[BOJ 16234/Java]인구 이동 (0) | 2023.08.17 |
[boj2493/Java] 탑 (0) | 2023.08.07 |
[SWEA2805/Java] 농작물 수확하기 (0) | 2023.08.01 |