이번 문제는 깊이 우선 탐색을 통해 해결할 수 있었다. 이 문제에서의 키 포인트는 우선 가장 앞의 열에서 가장 끝의 열로 이동한다는 점 (행에서 행이 아님)과 가장 위의 행부터 아래방향을 먼저 탐색해야 한다는 점이다.

우선 처음에 행과 열을 헷갈리는 바람에 삽질을 조금 했다. 이 부분은 문제를 다시 천천히 읽어보면서 고쳐나갔다.

아무리 생각해도 맞는 코드라고 생각했었지만 탐색의 순서 때문에 계속해서 틀린 답이 출력되었었다. 이 문제는 반드시 가장 위의 행부터 탐색할 경우에 오른쪽 아래 대각선부터 탐색해야만 한다.

이 그림에서 보이는 것 처럼 가장 위의 행에서 시작을 하면 오른쪽이나 오른쪽 아래 대각선으로밖에 이동할 수 없다. 위에서부터 가능한 경로를 먼저 잡아주어야 다음 행에서 갈 수 있는 경로를 맞게 찾아갈 수 있기 때문에 아래->옆->위 순으로 탐색해주어야 한다.

불변 객체인 문자열을 가변 객체인 리스트로 저장하여 방문한 뒤에는 다음에 방문할 수 없도록 'x'로 변경해주어 방문처리를 진행하였다. 방문처리 리스트를 따로 생성해도 되지만 이 방법보다는 훨씬 효율적이다.

• r, c를 입력받는다.
• graph를 선언한다.
• r만큼 반복하는 for문을 돌린다.
  -> graph를 리스트 형태로 입력받는다.
• 정답을 저장할 변수 answer를 0으로 선언한다.
• 파이프의 3개의 방향에 대한 정보를 dy, dx에 저장한다. 이때 오른쪽 아래 방향부터 저장되도록 주의한다.
• dfs함수를 y, x를 인자로 갖도록 선언한다.
  -> x가 c-1일 경우 True를 반환한다.
  -> 3번 반복하는 i에 대한 for문을 돌린다.
  --> ny를 y+dy[i]로 저장한다.
  --> nx를 x+dx[i]로 저장한다.
  --> 만약 ny가 0 이상, r미만이고, nx가 0이상, c미만이고, graph[ny][nx]가 '.'일 경우,
  ---> graph[ny][nx]를 'x'로 갱신한다.
  ---> 만약 dfs(ny, nx)가 True일 경우, True를 반환한다.
  -> False를 반환한다.
• r만큼 반복하는 i에 대한 for문을 돌린다.
  -> 만약 graph[i][0]이 '.'일 경우,
  --> 만약 dfs(i, 0)이 True일 경우,
  ---> answer를 1 증가시킨다.
• answer를 출력한다.

Code

r, c=map(int, input().split())
graph=[]
for _ in range(r):
    graph.append(list(map(str, input())))
answer=0
dy=[-1, 0, 1]
dx=[1, 1, 1]
def dfs(y, x):
    if x==c-1:
        return True
    for i in range(3):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<r and 0<=nx<c and graph[ny][nx]=='.':
            graph[ny][nx]='x'
            if dfs(ny, nx):
                return True
    return False
for i in range(r):
    if graph[i][0]=='.':
        if dfs(i, 0):
            answer+=1
print(answer)