[BOJ] 3109번 빵집

개요

도시에 있는 치킨집중 몇개를 폐업시켜 최대 이익을 낼 수 있는지 탐색하는 문제

문제링크

코드

import java.io.*;
import java.util.StringTokenizer;

public class Baekjoon3109 {
    static int[][] dir = { {-1,1},{0,1},{1,1} };  //오른쪽 위, 오른쪽, 오른쪽 아래
    static char[][] map;
    static int R, C;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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();

        int pipe = 0;
        for (int i = 0; i < R; i++) {
            if (map[i][0] == '.' && dfs(i, 0)) {
                pipe++;
            }
        }
        bw.write(pipe+"\n");
        bw.close();
    }

    // 지나간 경로 표시를 그대로 냅두는 이유
    // 도착에 실패했으면 - 다른 경로를 통해 이 루트를 다시 온다고 해도 도착 못하기 때문에 냅둠
    // 도착에 성공했으면 - 파이프라인이 연결되었으므로 다른 파이프라인이 겹치는걸 방지하기 위해 냅둠
    public static boolean dfs(int r, int c) {
        if (c == C - 1)
            return true;

        map[r][c] = 'x';

        for (int i = 0; i < dir.length; i++) {
            int dr = r + dir[i][0];
            int dc = c + dir[i][1];

            if (dr < 0 || dr >= R || dc < 0 || dc >= C || map[dr][dc] == 'x')
                continue;

            if (dfs(dr, dc))    //연결에 성공하면 true 반환
                return true;
        }
        return false;
    }

}

해결 과정

2차원 배열의 첫번쨰 열에서 마지막열에 도달할 수 있는 최대 경우의 수를 찾는 문제이다. 왼쪽에서 오른쪽으로 이동하는데 한번 이동한 공간은 막히는 것을 고려해야 하는데 처음에는 탐색하면서 도착유무를 확인하고 도착하지 못했으면 이동한 공간을 다시 비워주는 방식으로 했다.

하지만 이 방식으로 구현하니 TC를 통과못했는데 잘 생각해보니 R x C 지도에서 놓을 수 있는 최대 파이프라인의 개수는 R개이다.

파이프라인은 겹칠 수 없고 여러갈래로 갈라질 수 없으므로 이미 탐색을 했는데 갈 수 없다는 결과가 나오면 어차피 다른 경로를 통해 그 지점으로 와도 갈 수 없기 때문에 막힌 그대로 두어야 했다. 그래서 완성한 코드가 위의 코드이다.

결과