바닥 장식 – 실버 4

dfs 접근 방법

 

1. 어떤 요소에 접근하고 접근 후 값 변경하고 다음 접근 방식 선택

2. 반복 문을 사용하여 변경되지 않은 값 인식 해당 값부터 다시 조회. (해당 조회가 행 혹은 열의 길이를 초과했는지 항상 확인할 것)

* 반복 문 사용 이유 중 하나는 해당 조회를 함수에서 종료 시키는 것이 아닌 각 인자를 모두 조회하면 끝나게 하기 위함도 있다.

 

n, m = map(int, input().split())
room = [list(input())for _ in range(n)]

ans = 0
def dfs(i, j):
    if room[i][j] == '-':
      room[i][j] = 0 
# 0은 방문 처리한 것을 말하고 이후 조건문에서 해당 값은 무시된다. 즉 - 혹은 | 값을 인지하여 연속되는 값이 끝난 경우에 ans에 +를 하고 다시 조회하기를 반복하여 전체 값을 깉이 우선으로 탐색하는 것이다.
      if j < m - 1 and room[i][j+1] == '-':
        dfs(i, j + 1)
    elif room[i][j] == '|':
      room[i][j] = 0
      if i < n - 1 and room[i+1][j] == '|':
        dfs(i + 1, j)
    
for i in range(n):
    for j in range(m):
        if room[i][j]: 
# if 값은 0을 제외한 모든 값이 일단 true이다. 그렇기에 제일 처음은 무조건 +1이 된 체 room을 순회하게 된다.
            ans += 1
            dfs(i, j)
print(ans)