[백준] 1388번 : 바닥 장식 - python 풀이

문제 설명

 

코드

# DFS 함수 정의
def dfs(x, y):
    # 바닥 장식이 '-' 일 때
    if graph[x][y] == '-':
        graph[x][y] = 1 # 해당 노드 방문처리
        for _y in [1, -1]: # 좌우 노드가 '-' 모양인지 확인
            Y = y + _y
            # 좌우 노드가 주어진 범위를 벗어나지 않고 '-' 모양이라면 재귀함수 호출
            if (Y > 0 and 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 (X > 0 and X < n) and graph[X][y] == '|':
                dfs(X,y)

# n: 세로 크기 / m : 가로 크기
n, m = map(int,input().split())
graph = []
for _ in range(n): # 행의 개수만큼 입력
    graph.append(list(input()))
    
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) # 결과 출력

 

DFS 문제를 연습하고자 저는 DFS (= 깊이 우선 탐색) 방법으로만 풀었습니다.

 

나만의 문제 풀이

 ● graph 변수에 바닥 장식을 할 모양을 한 행씩 저장하여 2차원 그래프 형태를 만듭니다.

 ● (0,0) 위치를 탐색 시작 노드로 두고 탐색합니다. (0,0) 노드와 같은 모양인지 아닌지 확인하고 같다면 언제까지 (= 어느 깊이) 같은 모양인지 탐색하여 나무 판자의 개수를 확인합니다. 

 

 ● '-' 인 경우

1) 일단 방문한 노드를 방문 처리하여 반복하여 탐색하지 않게 한다. (1로 처리)

2) '-'인 경우 같은 행에 좌우가 같은 모양이면 하나의 나무 판자로 생각하므로 [1, -1]을 y 값과 연산하여 주어진 범위(0<y<m) 에 해당하는지와 모양이 '-' 인지 확인한 후 같다면 재귀 함수를 호출한다

3) 모양이 같은 경우 재귀 함수가 계속해서 반복되므로 count 값에는 영향을 끼치지 않아 하나의 나무 판자로 계산할 수 있다.

 

 ● '|'인 경우

1) 일단 방문한 노드를 방문 처리하여 반복하여 탐색하지 않게 한다. (1로 처리)

2) '|'인 경우 같은 열에 상하가 같은 모양이면 하나의 나무 판자로 생각하므로 [1, -1]을 x 값과 연산하여 주어진 범위(0<x<n) 에 해당하는지와 모양이 '-' 인지 확인한 후 같다면 재귀 함수를 호출한다

3) 모양이 같은 경우 재귀 함수가 계속해서 반복되므로 count 값에는 영향을 끼치지 않아 하나의 나무 판자로 계산할 수 있다.