[백준] 바닥 장식 : 1388번 - Python

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

1388번: 바닥 장식

 

 

 

문제를 풀면서 몰랐던 개념

 

DFS 알고리즘에 대한 개념

-> https://ye5ni.tistory.com/108 참고!

 

 

 

문제의 접근 방법

 

👀 '-' 모양의 나무 판자와 '|' 모양의 나무 판자를 나누어서 계산하기

👀 '-' 모양은 좌우(가로) 노드의 값을 비교하고 '|' 모양은 상하(세로) 노드의 값을 비교하기

👀 특정 조건을 만족해야 하는 탐색 기법의 경우에는 DFS를 사용하는 것이 유리함!

 

 

 

내가 막혔던 부분

 

💢 DFS 알고리즘 구현의 어려움

💢 변수에 공백을 할당하여 이전 값과 비교하는 것에 대한 아이디어

 

 

 

문제 풀이 방법

 

1. 알고리즘 없이 풀기

2. DFS 알고리즘을 사용하여 풀기

 

 

 

소스코드 (DFS 알고리즘을 사용한 풀이)

# 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 = map(int, input().split()) # 방 바닥의 세로 크기 n, 가로 크기 m
graph = []  # 2차원 리스트의 맵 정보 저장할 공간
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)

 

소스코드 (알고리즘 없이 구현한 풀이)

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

# '-'모양의 나무 판자 개수 계산
count = 0
for i in range(n):
    a = ''
    for j in range(m):
        if graph[i][j] == '-':
            if graph[i][j] != a:
                count += 1
        a = graph[i][j]

# 'ㅣ'모양의 나무 판자 개수 계산
for j in range(m):
    a = ''
    for i in range(n):
        if graph[i][j] == '|':
            if graph[i][j] != a:
                count += 1
        a = graph[i][j]

print(count)

 

 

 

 

 

Reference

https://firsteast.tistory.com/127