📚 3109 - 빵집

빵집

이해

그리디를 이용하자!
R : 행, C : 열
첫째 열에서 시작해야하고, 마지막 열에서 끝나야 한다.

✔ 방향
(1) ↗

• x-1, y+1로 이동

(2) ➡

• x, y+1로 이동

(3) ↘

• x+1, y+1로 이동

열을 기준으로 이동한다.
서로 겹치거나, 접할 수 없다.

✔ 구현

check 함수로 구현해보자!

check 재귀 함수(행, 열)

- 만약 행이 0보다 크고 (1)와 같이 (행-1, 열+1)이 `.`일 때
  - 다음 재귀 함수(행-1, 열+1) 결과가 `.`이 True라는 결과를 가지고 왔다면
  - True를 return 한다.
- (2)와 같이 (행, 열+1)이 `.`일 때
  - 다음 재귀 함수(행, 열+1) 결과가 `.`이 True라는 결과를 가지고 왔다면
  - True를 return 한다.
- 만약 행+1이 R(총 행 길이)보다 작고 (3)와 같이 (행+1, 열+1)이 `.`일 때
  - 다음 재귀 함수(행+1, 열+1) 결과가 `.`이 True라는 결과를 가지고 왔다면
  - True를 return 한다.
  

- 위 3가지 조건 중에 적어도 하나에 계속 해당하다, 열이 y-1번째(마지막 열)에 도착했다면 True를 return 한다. (지나갔다면 다시방문하지 못하게 체크해야한다.)
- 위 3가지 조건에 해당하지 않는다면 최종적으로 False를 return 한다.

이와 같이 진행된다.

다만, 소스 구현할 때 (1)와 (2)의 순서를 바꾸면 어떻게 될까?

- 만약 행이 0보다 크고 (1)와 같이 (행-1, 열+1)이 `.`일 때
  - 다음 재귀 함수(행-1, 열+1) 결과가 `.`이 True라는 결과를 가지고 왔다면
  - True를 return 한다.
- (2)와 같이 (행, 열+1)이 `.`일 때
  - 다음 재귀 함수(행, 열+1) 결과가 `.`이 True라는 결과를 가지고 왔다면
  - True를 return 한다.
  
를

- (2)와 같이 (행, 열+1)이 `.`일 때
  - 다음 재귀 함수(행, 열+1) 결과가 `.`이 True라는 결과를 가지고 왔다면
  - True를 return 한다.
- 만약 행이 0보다 크고 (1)와 같이 (행-1, 열+1)이 `.`일 때
  - 다음 재귀 함수(행-1, 열+1) 결과가 `.`이 True라는 결과를 가지고 왔다면
  - True를 return 한다.

이와 같이

문제에 나와있는 예제를 통해 (1), (2) 순서를 바꿔서 그림을 그려보면

문제 예제

.xx..
..x..
.....
...x.
...x.

위의 그림 : (1), (2) 순서 (원래 순서) 로 실행시
밑의 그림 : (2), (1) 순서로 실행시

(2), (1) 순서로 실행시 중간부터 파이프라인을 연결하게 되어 예상했던 결과를 얻지 못하게 된다.

그러므로, ↗ ➡ ↘ 와 같은 순서로 재귀 함수를 구현해야 한다.

소스

import sys

read = sys.stdin.readline

r, c = map(int, read().split())

graph = []
answer = 0

for i in range(r):
    graph.append(list(map(str, read().strip())))

def check_fun(row, col):
    # 방문한 곳은 다시 방문하지 못하게 한다. (확인한 곳은)
    graph[row][col] = 'a'

    # 위 3가지 조건 중에 적어도 하나에 계속 해당하다,
    # 열이 y-1번째(마지막 열)에 도착했다면 True를 return 해야한다.
    if col == c-1:
        return True

    # 만약 행이 0보다 크고 (1)와 같이 (행-1, 열+1)이 `.`일 때
    if row > 0 and graph[row-1][col+1] == '.':
        if check_fun(row-1,col+1):
            return True

    # (2)와 같이 (행, 열+1)이 `.`일 때
    if graph[row][col+1] == '.':
        if check_fun(row, col+1):
            return True

    # 만약 행+1이 R(총 행 길이)보다 작고 (3)와 같이 (행+1, 열+1)이 `.`일 때
    if row+1 < r and graph[row+1][col+1] == '.':
        if check_fun(row+1,col+1):
            return True

    # 위 3가지 조건에 해당하지 않는다면 최종적으로 False를 return 한다.
    return False

for i in range(r):
    if graph[i][0] not in 'X':
        if check_fun(i,0):
            answer += 1

print(answer)

💡 참고
소스가 이해 되지 않는다면, 그림을 그려보자!