백준 3109번: 빵집 (Java)

접근

https://www.acmicpc.net/problem/3109

3109번: 빵집

dfs 알고리즘을 이용하여 해결할 수 있는 문제였습니다.

1. 시작점을 0, 0 부터 r - 1, 0 까지 위에서 부터 아래로 탐색하므로, 해당 위치에서 최대한 효율적인 순서대로 탐색하기 위해 오른쪽 위, 오른쪽 중앙, 오른쪽 아래 순으로 탐색하게 해주었습니다.
2. 탐색을 진행하면서 파이프가 놓아진 위치는 파이프가 놓아졌기 때문에 다시 탐색할 필요가 없습니다. 그리고 탐색에 실패한 위치는 탐색이 완료되었는데도 불구하고 파이프가 이어지지 않았으므로, 다른 위치에서 해당 위치까지 연결된다고 해도 다시 실패할 것이므로 다시 탐색할 필요가 없습니다. 따라서 탐색을 진행하는데 있어 visited 배열을 다시 원복할 필요가 없습니다.
3. r, c 를 탐색하기 시작하면 총 2가지 경우를 탐색하고, 아니라면 false 를 리턴합니다. 첫번째로 c == C - 1 일 경우, 파이프가 완성되었으므로 true를 리턴합니다. 두번째로 해당 위치에서 이동할 수 있는 3가지 위치(오른쪽 위, 오른쪽 중앙, 오른쪽 아래)를 탐색하여 이동할 수 있는 위치라면 해당 위치를 재귀 호출하여 해당 값이 true 라면 true를 리턴합니다.

코드

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

public class Main {

  static int R, C, ans;
  static char[][] map;
  static int[] dr = { -1, 0, 1 };
  static int[] dc = { 1, 1, 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());
    map = new char[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);
      }
    }
    br.close();
    for (int i = 0; i < R; i++) {
      if (dfs(i, 0)) ans++;
    }
    System.out.println(ans);
  }

  static boolean dfs(int r, int c) {
    map[r][c] = '-';
    if (c == C - 1) return true;
    for (int i = 0; i < 3; i++) {
      int nr = r + dr[i];
      int nc = c + dc[i];
      if (0 <= nr && nr < R && map[nr][nc] == '.') {
        if (dfs(nr, nc)) return true;
      }
    }
    return false;
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!