[baekjoon] 백준 1388번(파이썬): 바닥 장식

문제

1388번: 바닥 장식

- 형택이는 건축가이다.

- 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다.

- 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다.

- 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다.

- 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

- 이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다.

- 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고,

- 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

- 기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 구하는 문제이다.

- 방 바닥의 세로 크기N과 가로 크기 M이 주어진다.

- N개의 줄에 M개의 문자가 주어진다.

- 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M의 제한은 100이다.

알고리즘

- 가로 문양의 바닥과 세로 문양의 바닥을 탐색하기 위해 두개의 dfs 탐색으로 수행한다.

코드

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드


# DFS로 가로 노드를 방문하고 연결된 모든 노드들도 방문
def dfs_horizontal(x, y):

    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False

    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == "-":

        # 해당 노드 방문 처리
        graph[x][y] = "x"

        # 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs_horizontal(x, y - 1)
        dfs_horizontal(x, y + 1)

        return True
    return False


# DFS로 세로 노드를 방문하고 연결된 모든 노드들도 방문
def dfs_vertical(x, y):

    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False

    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == "|":

        # 해당 노드 방문 처리
        graph[x][y] = "x"

        # 상, 하의 위치들도 모두 재귀적으로 호출
        dfs_vertical(x - 1, y)
        dfs_vertical(x + 1, y)

        return True
    return False


n, m = map(int, sys.stdin.readline().split())

graph = []
for _ in range(n):
    graph.append(list(sys.stdin.readline()))

cnt = 0
# n 세로, m 가로
for i in range(n):
    for j in range(m):
        if graph[i][j] == "-":
            dfs_horizontal(i, j)
            cnt += 1
        elif graph[i][j] == "|":
            dfs_vertical(i, j)
            cnt += 1

print(cnt)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법