[python] 백준 3109번 : 빵집

<문제>

https://www.acmicpc.net/problem/3109

3109번: 빵집

<풀이>

그리디 문제인데 dfs를 곁들인. 여기서는 오른쪽 위부터 오른쪽, 오른쪽 아래 순으로 방문하도록 하여 목적을 챙긴다.

DFS 를 재귀적으로 써서 각 출발점에서 끌열(도착지)까지 가도록 한다.

다음 좌표로 갈 때에는 갈수 있는지(x가 아닌지), 범위 확인, 방문여부 확인(visited 배열) 을 한다. 

이 때 방문한 걸로 표시되었지만 못 가는 길이라 가려던 것을 취소해야하는 길에 대해서는 왜 방문여부를

미방문으로 정정하지 않는지에 대한 의문은... 어차피 못 갈 길이니 무시하는 것 같다. 

명확한 설명이 가능한 이들은 댓글을 달아주길...

도착 시에는 true 를 return 하고, 그 겉(?) 함수역시 true를 return 하면서 첫 출발좌표까지 간다.

이로써 각 출발점(첫 열)에서 갈 수 있는 길(true) 이라면 파이프를 설치+1 하여 결과를 나타낸다.

<소스코드>

r,c = map(int, input().split())
## r행 c열
board = []
visited = [[-1]*c for _ in range(r)]
answer = 0
for _ in range(r):
  board.append(list(input()))

def dfs(cr,cc):
  if cc == c-1:
    return True
  for dr in [-1,0,1]: ##
    nr = cr + dr
    nc = cc + 1
    if 0 <= nr < r and 0 <= nc < c:
      if board[nr][nc] != 'x' and visited[nr][nc] == -1:
        visited[nr][nc] = 1
        # 의문 : 방문표시해두었으나 안 간 좌표에 대한 visited는 왜 정정하지 않지? => 어차피 가도 false 였을테니까
        if dfs(nr,nc):
          return True
        # dfs(nr,nc) # 이렇게 하면 뚝 끊김. 이전 길에서 true 였으면 반영해서 return 해줘야 출발지기준 true가 됨
  return False

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

print(answer)