문제

R*C의 빵집 지도에서 첫 열은 근처 빵집의 가스관, 마지막 열은 원웅이의 빵집을 나타낸다. 이때 건물이 있는 (1인 곳)을 피해 근처 빵집과 원웅 빵집을 연결해야한다. 되도록 많은 가스관을 연결할 수 있는 경우의 수를 구한다.

풀이

처음에는 BFS로 풀이했는데 생각해보니 한 열에서 가스관 설치를 시작할 때 한 루트로만 가야하기 때문에 DFS가 더 적합할 것이라고 판단했다.

처음에 for문을 순회하면서 맨 처음 열부터 DFS를 수행해준다.

DFS에서는 x를 {-1, 0, 1}, y는 +1만큼씩 변경시키면서 범위 내에 존재하고 건물이 아닌 블록에 가스관을 설치한다.

y의 값이 맨 오른쪽 (c-1)과 동일해졌을때는 count를 증가시켜주고 DFS를 종료한다.

이때 x, y를 움직일 수 없는 경우에는 return false으로 더이상 탐색할 수 없도록 한다.

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_3109 {
    static int[][] map;
    static int r;
    static int c;
    static int count;
    static int[] dx = {-1, 0, 1};

    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 int[r][c];

        for (int i = 0; i < r; i++) {
            String[] input = br.readLine().split("");
            for (int j = 0; j < c; j++) {
                if (input[j].equals(".")) {
                    map[i][j] = 0;
                } else {
                    map[i][j] = 1;
                }
            }
        }

        count = 0;

        for (int i = 0; i < r; i++) {
            dfs(i, 0);
        }

        System.out.println(count);
    }

    static boolean dfs(int x, int y) {
        for (int i = 0; i < 3; i++) {
            int nx = x + dx[i];
            int ny = y + 1;

            if (nx < 0 || ny < 0 || nx >= r || ny >= c) {
                continue;
            }

            if (map[nx][ny] == 0) {
                if (ny == c - 1) {
                    map[nx][ny] = 2;
                    count++;
                    return true;
                }

                map[nx][ny] = 2;
                if (dfs(nx, ny)) {
                    return true;
                }
            }
        }
        return false;
    }

    static void print() {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }
}

후기

중간에 탐색을 더이상 진행하지 않아도 될 부분을 어떻게 해야할지 몰라 검색해서 풀었다.
아직도 감이 잘 안오지만 for문을 돌아도 진행할 수 없는 경우는 종료 해야 한다는 것은 이해했다!