[DFS/BFS] 백준 1388번 : 바닥 장식

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

1388번: 바닥 장식

 

DFS 활용해서 풀어야할 것 같은 문제!

하지만 사실 DFS를 사용하지 않고도 풀 수 있다고 한다. 일단 DFS 공부를 위해 해당 방법을 통해 풀어보자.

dfs 함수 설명

- 일때는 좌우를 확인해서 또 - 라면 재귀적으로 함수를 호출한다.

| 일때도 마찬가지로 상하를 확인해서 또 | 라면 재귀적으로 함수를 호출한다.

이때 함수에서 나오게된 경우에는 한개의 막대기가 끊겼다는 의미이기 때문에 count += 1을 해준다.

 

# 입력 부분 
n,m = map(int, input().split()) # 세로:n, 가로:m
graph = []  # 2차원 리스트의 맵 정보 저장할 공간
for _ in range(n):
    graph.append(list(input()))

def dfs(x,y):
    if graph[x][y] == '-':
        graph[x][y] = 1	    # 해당 노드 방문처리
        for _y in [1,-1]:   # 양옆(좌우) 확인하기
            Y = y + _y
            # 좌우 노드가 주어진 범위를 벗어나지 않고 '-'모양이라면 재귀함수 호출
            if (0 < Y < m) and graph[x][Y] == '-':
                dfs(x,Y)
    if graph[x][y] == '|':
        graph[x][y] = 1	    # 해당 노드 방문처리
        for _x in [1,-1]:   # 상하(위아래) 확인하기
            X = x + _x  # 이동하기
            # 상하 노드가 주어진 범위를 벗어나지 않고 '|' 모양이라면 재귀함수 호출
            if (0 < X < n) and graph[X][y] == '|':
                dfs(X,y)
 
count = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == '-' or graph[i][j] == '|':
            dfs(i,j)    # 노드가 '-'이나 '|'일 경우에 재귀함수 호출
            count += 1
 
print(count)

 

파이썬에서 _로 시작하는 변수는 보통 사용하지 않는 변수를 뜻함

입력 받는 부분 구조 외우기