백준 1388번 풀이 - 파이썬(Python) (그래프 탐색 / DFS / BFS)

난이도 : 실버3

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

1388번: 바닥 장식

 

문제

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

 

 

---

나의 풀이 (DFS, 재귀함수 활용)

import sys
n, m = map(int, sys.stdin.readline().split())	# 그래프 크기 입력

# 그래프 입력 받기
graph = []
for i in range(n):
    graph.append(list(input()))

visited = [[0] * m for _ in range(n)]

# 세로 나무 판자에 대한 DFS 재귀 함수
def dfs1(r, c):
    if r >= n or c >= m:
        return False
    if visited[r][c] == 0 and graph[r][c] == '|':
        visited[r][c] = 1
        dfs1(r + 1, c)
        return True
    return False

# 가로 나무 판자에 대한 DFS 재귀 함수
def dfs2(r, c):
    if r >= n or c >= m:
        return False
    if visited[r][c] == 0 and graph[r][c] == '-':
        visited[r][c] = 1
        dfs2(r, c + 1)              
        return True
    return False

result = 0
# 전체 위치에 대해 DFS 함수 반복
for i in range(n):
    for j in range(m):
		# DFS 함수가 True를 반환하면 result += 1
        if dfs1(i, j) == True or dfs2(i, j) == True:
            result += 1
            # 해당 round의 탐색 결과를 비교하기 위해 visited를 출력
            # for k in range(n):
            #     print(visited[k])
            # print('------')

print(result)

BFS 문제를 찾아 들어가서 BFS로 풀려고 했으나,

풀이법 떠올리기도 쉽지 않고, queue를 능숙하게 구현하기도 어려워서

나도 모르게 익숙한 DFS 재귀함수로 풀이해버렸다.

 

가로 또는 세로 방향으로 이어진 나무 판자를 묶어서 1개를 count하는 것이므로,

재귀함수를 두 개 설정하여

한 개는 가로 나무판자의 같은 방향 여부를 오른쪽으로 가면서 탐색하도록,

다른 한 개는 나무판자의 같은 방향 여부를 아래쪽으로 가면서 탐색하도록 구현하였다.

오른쪽과 아래쪽으로 한정하지 않고, 상하 또는 좌우를 탐색하도록 구현했어도,

어차피 이미 탐색한 결과가 기록되어 왼쪽 또는 위쪽으로 움직이는 일은 없었을 것이다.

(근데 이건 다른 DFS 문제도 마찬가지 아닌가..?)

 

남의 풀이가 궁금해진다.

 

 

 

 

 

남의 풀이1 (BFS 활용)

from collections import deque

n, m = map(int, input().split())	# 그래프 크기 입력
result = 0

graph = [list(input()) for _ in range(n)]	# 나무 판자 그래프 정보 입력
visited = [[0] * m for _ in range(n)]	# 방문 여부 그래프 초기화

# BFS 함수 선언
def bfs(r, c):
    queue = deque([(r, c)])
    
    # queue가 비어있지 않다면 계속 반복
    while queue:
        r, c = queue.popleft()
		# 위치가 오류라면 continue
        if r < 0 or r >= n or c < 0 or c >= m:
            continue
		# 이미 방문한 위치라면 continue
        if visited[r][c] == 1:
            continue
		
        # 가로 판자에 대한 로직
        if graph[r][c] == '-':
            visited[r][c] = 1	# 방문 정보 저장
            # 좌 또는 우에 대하여, 가능한 위치인지 판단하고
            # 같은 방향의 나무 판자라면 queue에 추가
            if c - 1 >= 0:
                if graph[r][c - 1] == '-':
                    queue.append((r, c - 1))
            if c + 1 < m:
                if graph[r][c + 1] == '-':
                    queue.append((r, c + 1))
                    
		# 세로 판자에 대한 로직 - 가로와 동일
        if graph[r][c] == '|':
            visited[r][c] = 1
            if r - 1 >= 0:
                if graph[r - 1][c] == '|':
                    queue.append((r - 1, c))
            if r + 1 < n:
                if graph[r + 1][c] == '|':
                    queue.append((r + 1, c))
            
# 전체 위치에 대해 BFS 함수 적용
for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            bfs(i, j)
            result += 1

print(result)

BFS와 큐 자료구조를 이용한 풀이이다.

확실히 DFS, 재귀함수로 푼 것이나 로직은 큰 차이가 없다.

 

어떤 알고리즘을 사용했을 때 탐색이 일어나는 순서와 로직이 머릿속으로 그려지기만 한다면,

가능한 문제에서는 어느 알고리즘을 사용해도 상관 없는 듯하다.

 

 

 

 

 

 

남의 풀이2 (알고리즘 활용 X)

# 방 바닥의 세로 크기 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)

와 .. 너무 간단하다.

5 x 7 크기의 그래프를 가정하면

각 행을 오른쪽으로, 각 열을 아래쪽으로 총 12번 이동하면서

연결된 판자는 1개로 세고, 다른 방향의 판자가 나오면 판별자를 초기화하는 식으로 구현한 풀이이다.

 

간단한 구현 문제가 되었다..