Point 💡

• 행이 아닌 열을 이용한다!

• DFS을 사용할 때 반드시 종료조건 먼저 생각하기

• 0행 ~ 마지막 행까지 탐색하기 때문에 반드시 위쪽으로 붙어서 경로를 선택해야 다음 출발주자의 도달 가능성을 해치지 않는다.

  → 오른쪽 위, 오른쪽, 오른쪽 아래 순서로 탐색하자! Greedy

if dfs(nx, ny):
		return True

• dfs(nx, ny)만 해주면 될 것 같은데 왜 한번 더 확인해야하는지 계속 고민했다.

  → 해당 출발지에서 갈 수 있는 최적의 경로가 등장했다면 더 이상 재귀적인 탐색을 하지 않아야하기 때문이다.

• dfs(nx, ny)만 해줄 경우, 이동 가능한 모든 경우의 수를 탐색하기 때문에 최적의 경로가 발견되어도 이를 확인하거나 종료하지 않고 계속해서 다른 경로를 탐색하므로, 답이 달라진다.

Python Solution

import sys
r, c = map(int, sys.stdin.readline().split())

graph = []
for _ in range(r):
    graph.append(list(sys.stdin.readline().rstrip()))

dx = [-1, 0, 1]
dy = [1, 1, 1]

visited = [[-1 for _ in range(c)] for _ in range(r)]
cnt = 0

def dfs(x, y):
    # dfs는 종료조건을 먼저 생각하기
    if y == c-1:
        return True

    for i in range(3):
        nx, ny = x + dx[i], y + dy[i]

        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] != 'x' and visited[nx][ny] == -1:
                visited[nx][ny] = 1
                # 해당 출발지에서 갈 수 있는 최적의 경로가 등장했다면 더 이상 재귀적인 탐색을 하지 않는다.
                if dfs(nx, ny):
                    return True
    return False

for i in range(r):
    if dfs(i, 0):
        cnt += 1

print(cnt)

Java Solution

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

public class Main {

    static char[][] graph;
    static int r;
    static int c;
    static int count;
    static int[][] visited;
    static int[] dx;
    static int[] dy;

    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());

        graph = new char[r][c];
        for (int i=0; i<r; i++){
            graph[i] = br.readLine().toCharArray();
        }

        dx = new int[]{-1, 0, 1};
        dy = new int[]{1, 1, 1};

        visited = new int[r][c];
        for (int i = 0; i<r; i++){
            for (int j = 0; j<c; j++) {
                visited[i][j] = -1;
            }
        }

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

        System.out.println(count);

    }

    public static boolean dfs(int x, int y) {
        if (y == c-1) {
            return true;
        }

        for (int i=0; i<3; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx &&  nx < r && 0 <= ny && ny < c) {
                if (graph[nx][ny] != 'x' && visited[nx][ny] == -1) {
                    visited[nx][ny] = 1;
                    if (dfs(nx, ny)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
}