[Problem Solving] BOJ 3109 : 빵집

문제 링크 : https://www.acmicpc.net/problem/3109

 

R*C 그래프에서 graph[i][0]에서 graph[j][C - 1]까지 갈 수 있는 서로 겹치지 않는 경로의 최대 개수를 구하는 문제이다.

 

graph[i][0]에서 시작되는 dfs를 수행하여 경로의 수를 구한다.

 

서로 겹치지 않는 경로의 최대 개수를 구해야 하기 때문에 이동 경로의 우선 순위를 {오른쪽 상단 -> 오른쪽 -> 오른쪽 하단}으로 설정한다. 위에 있는 시작점에서 최대한 위로 가려고 해야 밑에 있는 시작점으로 출발하는 dfs를 수행 시 갈 수 있는 선택지가 많아지기 때문이다.

 

graph[j][C - 1]에 도달했다면 answer를 1 증가시키고 true를 return하면, graph[j][C - 1]부터 graph[i][0]까지 경로에 true가 전파되고 dfs가 종료된다. 해당 경로에 대한 visited는 true이기 때문에 다음 graph[i][0]에 대한 dfs에서는 이미 방문한 길을 갈 수 없다.

 

이런 식으로 서로 겹치치 않는 경로의 최대 개수를 구해서 출력하면 된다.

 

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

public class Main 
{
    public static class Point
    {
        public int y;
        public int x;

        public Point(int y, int x)
        {
            this.y = y;
            this.x = x;
        }
    }
    public static int R;
    public static int C;
    public static char[][] graph;
    public static boolean[][] visited;
    public static int answer = 0;
    public static int dy[] = {-1, 0, 1};
    public static int dx[] = {1, 1, 1};

    public static boolean valid(Point p)
    {
        return (0 <= p.y && p.y < R && 0 <= p.x && p.x < C && graph[p.y][p.x] != 'x' && !visited[p.y][p.x]);
    }

    public static boolean dfs(Point cur)
    {
        boolean arrived = false;
        visited[cur.y][cur.x] = true;
        if(cur.x == C - 1)
        {
            answer += 1;
            return true;
        }
        for(int i = 0; i < 3; i++)
        {
            Point next = new Point(cur.y + dy[i], cur.x + dx[i]);
            if(valid(next))
            {
                arrived = dfs(next);
            }
            if(arrived)
            {
                return true;
            }
        }
        return false;
    }

    public static void input() throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        R = Integer.parseInt(line[0]);
        C = Integer.parseInt(line[1]);
        graph = new char[R][C];
        visited = new boolean[R][C];
        for(int i = 0; i < R; i++)
        {
            String row = br.readLine();
            for(int j = 0; j < C; j++)
            {
                graph[i][j] = row.charAt(j);
                visited[i][j] = false;
            }
        }
        br.close();
    }

    public static void solution()
    {
        for(int i = 0; i < R; i++)
        {
            Point start = new Point(i, 0);
            dfs(start);
        }
    }

    public static void output()
    {
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException
    {
        input();
        solution();
        output();
    }
}