[파이썬/Python] 백준 1388번: 바닥 장식

숨·2024년 7월 14일

코테

알고리즘 문제 풀이

목록 보기

30/105

📌 문제 : 백준 1388번

📌 문제 탐색하기

N : 방 바닥 세로 크기 (1 ≤ N ≤ 50)
M : 방 바닥 가로 크기 (1 ≤ M ≤ 50)

✅ 입력 조건
1. N,M 공백으로 구분해 입력
2. N번 반복해 M개의 문자 입력
3. -가 같은 행에 인접하면 같은 나무 판자
4. |가 같은 열에 인접하면 같은 나무 판자
✅ 출력 조건
1. 바닥 장식에 필요한 나무 판자 개수 출력

입력받은 바닥 장식 모양을 확인하면서 나무 판자 개수를 세야 한다.

-이면 인접하면서 같은 행에 -가 있는지 확인해야 하고,
있다면 또 다른 무늬가 나올 때까지 인접하면서 같은 행에 -가 있는지 확인하는 과정을 반복해서 진행해야한다.
|도 마찬가지로 반복하면서 다른 무늬가 나올 때까지 확인해야 한다.

하나의 입력에 대해 다른 무늬가 나올 때까지 같은 무늬를 찾아가는 과정을 반복해야 하므로, DFS를 이용해 재귀적으로 작동하도록 구현한다.

전체 바닥 장식을 입력받아 좌표 형식으로 접근할 수 있도록 저장한다.
확인한 바닥 장식임을 표시하기 위해 해당 값을 0으로 바꾸어 방문 처리한다.

장식이 -일 경우와 |일 경우를 나눈다.
전체 바닥 범위 내에서 다른 방식으로 이동하며 같은 바닥 장식이 있는지 확인한다.
바닥의 맨 왼쪽 위부터 차례로 확인할 것이므로 한쪽 방향으로만 이동한다.

- → 오른쪽으로 이동
| → 아래로 이동

DFS 과정이 끝나면 횟수를 1 더하는 식으로 판자 개수를 센다.

가능한 시간복잡도

전체 바닥 장식 확인 → $O(N * M)$
DFS → $O(N * M)$

최종 시간복잡도
$O(N * M)$ 이므로 최악의 경우 $O(50^2)$ 로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

DFS로 같은 무늬 재귀적 탐색

📌 코드 설계하기

N, M 입력
바닥 장식 입력
DFS 함수 구현
3-1. 방문 처리
3-2. '-'이면 오른쪽 확인
3-3. '|'이면 아래 확인
개수 저장 변수 정의
전체 바닥 장식 확인
원하는 형식으로 출력

📌 시도 회차 수정 사항

1회차

    # 3-1. '-'이면 방문처리 후 범위 내의 오른쪽 확인
    if floor[x][y] == '-':
        floor[x][y] = 0

        if x + 1 < N and floor[x + 1][y] == '-':
            dfs(x + 1, y)

    # 3-3. '|'이면 방문처리 후 범위 내의 아래 확인
    elif floor[x][y] == '|':
        floor[x][y] = 0

        if y + 1 < M and floor[x][y + 1] == '|':
            dfs(x, y + 1)

예제 2 결과에서 IndexError: list index out of range가 발생했다.
인접한 같은 모양의 장식이 있는지 확인하기 위해 해당 위치에 접근하는 조건문을 반대로 작성해서 발생하는 에러였다.

    # 3-1. '-'이면 방문처리 후 범위 내의 오른쪽 확인
    if floor[x][y] == '-':
        floor[x][y] = 0

        if y + 1 < M and floor[x][y + 1] == '-':
            dfs(x, y + 1)

    # 3-3. '|'이면 방문처리 후 범위 내의 아래 확인
    elif floor[x][y] == '|':
        floor[x][y] = 0

        if x + 1 < N and floor[x + 1][y] == '|':
            dfs(x + 1, y)

조건문을 수정했다.

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. N, M 입력
N, M = map(int, input().split())

# 2. 바닥 장식 입력
floor = [list(input().rstrip()) for _ in range(N)]

# 3. DFS 함수 구현
def dfs(x, y):
    # 3-1. '-'이면 방문처리 후 범위 내의 오른쪽 확인
    if floor[x][y] == '-':
        floor[x][y] = 0

        if y + 1 < M and floor[x][y + 1] == '-':
            dfs(x, y + 1)

    # 3-3. '|'이면 방문처리 후 범위 내의 아래 확인
    elif floor[x][y] == '|':
        floor[x][y] = 0

        if x + 1 < N and floor[x + 1][y] == '|':
            dfs(x + 1, y)

# 4. 개수 저장 변수 정의
count = 0

# 5. 전체 바닥 장식 확인
for i in range(N):
    for j in range(M):
        if floor[i][j] != 0:
            dfs(i, j)
            count += 1

# 6. 원하는 형식으로 출력
print(count)