[DFS] Sliver 4 1388 바닥장식

문제

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

 

---

설계 ✨

1.  왜 그래프 탐색 알고리즘을 썼는가?

일단, | | (세로 판자)는 상하로 2개,  -- (가로 판자)는 좌우로 2개 붙어있으면

판자를 1개를 본다는 점에서 그래프 탐색 알고리즘이 떠올랐다. 

예시를 보면, 판자가 2개 이상이면 판자 1개로 보는 것을 알 수 있다.

판자를 1개로 본다는 것은 탐색을 통해 조건에 맞는 묶음을 찾고, 그 묶음을 카운트한다는 뜻이기 때문이다.  

 

2.  DFS vs BFS

어느 것으로 풀어도 비슷할 것 같다.

 

3.  2차원 리스트에서의 탐색 

위치리스트를 설정해주었다.

| 판자는 열대로 탐색해야하므로 2차원 리스트 graph[x][y]에서 x좌표에 +1 (위),  -1 (아래)를 더해 상하로 이동한 좌표에 대해 탐색하도록 설계했다.

- 판자는 행대로 탐색해야하므로 2차원 리스트 graph[x][y]에서 y좌표에 +1 (좌) ,-1 (우)를 더해 좌우로 이동한 좌표에 대해 탐색하도록 설계했다.

이때 원래 좌표에서 더해주는 것이므로 범위가 벗어나지 않도록 범위 설정이 필요하다.  

---

위의 설계에 따라 다음과 같은 코드를 작성하였다. 

처음에 틀렸습니다가 뜨길래 알고리즘도 다 맞는데, 왜 안되는지 계속 고민하였다.

영어 l을 써서 틀린 것이었다. 

준혁아 고마워  

# 1388 바닥장식
# 문제 이해하는데 조금 오래 걸림
#  ㅣㅣ (세로 판자) 또는 -- (가로 판자) 2개 붙어있으면 
# 판자를 1개로 본다.
# '-'는 행대로, 'ㅣ'는 열대로 탐색해야함
# dfs 이용
# 영어 l 웬수같은 놈

def dfs(graph,x,y):
  dx = [1,-1]
  dy = [1,-1]

  if graph[x][y] == '|':# 세로판자면
    graph[x][y] = '.' # 방문처리 # 정신차리자.. '==' 아니야..
    for i in range(2):
      X = x + dx[i] # 상하로 탐색
      if 0<=X<n and graph[X][y] == '|': # 범위제한
        dfs(graph,X,y) # 재귀 호출

  if graph[x][y] == '-': 
    graph[x][y] = '.' # 방문처리 
    for i in range(2):
      Y = y + dy[i] # 좌우로 탐색
      if 0<=Y<m and graph[x][Y] == '-': # 범위 제한
        dfs(graph,x,Y) # 재귀 호출 
   
            
        

n,m = map(int,input().split())
graph = [list(input()) for i in range(n)]
count = 0 

for i in range(n):
  for j in range(m):
    if graph[i][j] == '|' or graph[i][j] == '-':
      dfs(graph,i,j)
      count += 1 # 탐색이 끝나면 판자개수 추가 

print(count)