개발이야기/코딩테스트

[백준-1338(DFS)]바닥장식

Study & Stack 2025. 6. 5. 11:32
728x90

문제 바로가기

문제

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

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

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

입력

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

 

출력

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

예제 입력

4 4
----
----
----
----

예제 출력

4

예제 입력

6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-

예제 출력

31

예제 입력

7 8
--------
|------|
||----||
|||--|||
||----||
|------|
--------

예제 출력 

13

예제 입력

10 10
||-||-|||-
||--||||||
-|-|||||||
-|-||-||-|
||--|-||||
||||||-||-
|-||||||||
||||||||||
||---|--||
-||-||||||

예제 출력

41

예제 입력 

6 6
-||--|
||||||
|||-|-
-||||-
||||-|
||-||-

예제 출력

19

문제 요약

바닥이 -(가로 나무 판자), |(세로 나무 판자)로 이루어진 직사각형 모양이고,
연결된 같은 모양의 나무 판자를 하나의 조각으로 세는 문제입니다.

 문제의 핵심 개념

  1. **같은 모양의 판자가 연속되어 있는 경우 "하나의 조각"**으로 본다.
  2. - 는 가로로 연속되어 있어야 하나의 조각.
  3. | 는 세로로 연속되어 있어야 하나의 조각.
  4. 단, 가로와 세로가 엇갈려 있으면 서로 다른 조각으로 본다.

핵심 알고리즘: DFS (깊이 우선 탐색) 또는 BFS

  • 같은 모양(-, |)이 연결된 구간을 찾아서 "한 번만 세면" 되므로,
    → 탐색 후 방문 표시해서 중복 계산을 막는 것이 핵심입니다.

접근 방식 요약

  1. 입력 처리: 바닥 상태를 2차원 리스트로 저장한다.
  2. 방문 배열: 이미 탐색한 칸은 다시 탐색하지 않도록 체크한다.
  3. 전체 칸을 순회:
    • 아직 방문하지 않은 칸이 있다면,
    • DFS를 이용해 해당 조각 전체를 탐색하고,
    • 조각 수(count)를 1 증가시킨다.
  4. DFS 조건:
    • -: 오른쪽으로만 연결
    • |: 아래쪽으로만 연결
import sys  # 시스템 관련 기능을 사용하기 위한 모듈

input = sys.stdin.readline  
# 입력 속도를 빠르게 하기 위해 readline 사용 (입력이 많을 경우 시간 단축됨)

n, m = map(int, input().split())  
# 첫 줄에서 세로(n)와 가로(m)의 크기를 입력 받음
# 예: 4 4 → n=4, m=4

# 바닥 장식 데이터를 저장할 2차원 리스트 생성
board = []  # 예: [['-', '-', '-', '-'], ['-', '-', '|', '-'], ...]

for _ in range(n):  # 세로 길이만큼 반복
    line = input().strip()  # 줄바꿈(\n)을 제거한 문자열을 한 줄 입력 받음
    row = list(line)        # 문자열을 한 글자씩 잘라 리스트로 변환
    board.append(row)       # 완성된 한 줄 리스트를 board에 추가

# 방문한 위치를 체크할 2차원 리스트 생성 (초기값은 모두 False)
visited = [[False] * m for _ in range(n)]
# 예: [[False, False, False, False], ..., 총 n줄]

# DFS 함수 정의: 현재 좌표(x, y)를 기준으로 같은 조각을 탐색
def dfs(x, y):
    visited[x][y] = True  # 현재 좌표 방문 처리

    current = board[x][y]  # 현재 위치의 타일이 '-'인지 '|'인지 확인

    if current == '-':  # 수평 타일인 경우
        ny = y + 1  # 오른쪽 방향으로 이동
        # 범위를 벗어나지 않고, 아직 방문하지 않았으며, 같은 수평 타일인 경우
        if ny < m and not visited[x][ny] and board[x][ny] == '-':
            dfs(x, ny)  # 재귀적으로 오른쪽으로 계속 탐색

    elif current == '|':  # 수직 타일인 경우
        nx = x + 1  # 아래쪽 방향으로 이동
        # 범위를 벗어나지 않고, 아직 방문하지 않았으며, 같은 수직 타일인 경우
        if nx < n and not visited[nx][y] and board[nx][y] == '|':
            dfs(nx, y)  # 재귀적으로 아래쪽으로 계속 탐색

# 결과: 조각 개수를 저장할 변수
count = 0

# 전체 board를 돌면서 아직 방문하지 않은 타일에 대해 DFS 수행
for i in range(n):  # 세로 방향 반복
    for j in range(m):  # 가로 방향 반복
        if not visited[i][j]:  # 아직 방문하지 않았다면
            dfs(i, j)  # DFS 탐색 시작
            count += 1  # 새로운 조각이므로 개수 +1

# 결과 출력
print(count)
728x90