[BOJ] 바닥 장식 - 1388 (S4)

시간 제한	메모리 제한
2 초	128 MB

문제

형택이는 건축가이다. 지금 형택이는 바닥 장식 공사를 하려고 한다. 바닥은 N개의 행과 M개의 열로 이루어진 직사각형 모양이다.

바닥을 장식하는 방법은 아주 간단하다. 바닥 타일은 -와 | 두 종류가 있다. -인 경우에는 가로로 연속해서 붙일 수 있고, |인 경우에는 세로로 연속해서 붙일 수 있다.

바닥은 이미 장식이 되어있는데, 형택이는 개수를 세어보기로 했다. 이미 장식되어있는 바닥에 사용된 타일의 개수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 M개의 문자가 주어진다. 이것은 바닥의 장식을 나타낸다. (1 ≤ N, M ≤ 100)

출력

첫째 줄에 타일의 개수를 출력한다.

풀이

이 문제는 연결된 타일을 하나의 타일로 세는 문제이다. -는 가로로만 연결되고, |는 세로로만 연결된다.

접근 방법

연속된 같은 종류의 타일을 하나의 타일로 세어야 하므로, 그래프 탐색(BFS 또는 DFS)을 사용하거나 단순히 방향성을 고려한 탐색을 할 수 있다.

각 타일 종류마다 탐색 방향이 고정되어 있다:

• - 타일: 가로 방향 (→)
• | 타일: 세로 방향 (↓)

풀이 과정

1. 전체 바닥을 순회한다.
2. 아직 방문하지 않은 타일을 만나면, 해당 타일의 종류에 따라 한 방향으로만 탐색한다.
3. 같은 종류의 타일이 연속되는 동안 방문 처리를 하고 계속 진행한다.
4. 다른 타일을 만나거나 범위를 벗어나면 하나의 타일로 카운트한다.

BFS를 이용한 구현

BFS를 사용하여 연결된 타일을 탐색하되, 타일 종류에 따라 탐색 방향을 제한한다.

코드

from collections import deque

N, M = map(int, input().split())

floor = [list(input()) for _ in range(N)]

def search_tiles(start, visited, tile_shape):
    # 타일 모양에 따라 탐색 방향 설정
    if tile_shape == '-':
        dy, dx = 0, 1
    else:
        dy, dx = 1, 0

    q = deque([start])
    while q:
        y, x = q.popleft()

        ny, nx = y + dy, x + dx

        # 범위 벗어났을 경우
        if not (0 <= ny < N) or not (0 <= nx < M):
            return 1
        # 이미 방문했을 경우
        if visited[ny][nx]:
            return 1
        # 타일 모양이 다를 경우
        if floor[ny][nx] != tile_shape:
            return 1

        q.append((ny, nx))
        visited[ny][nx] = True

visited = [[False] * M for _ in range(N)]
tile_cnt = 0

for y in range(N):
    for x in range(M):
        if visited[y][x]:
            continue
        tile_cnt += search_tiles((y, x), visited, floor[y][x])

print(tile_cnt)

코드 설명

search_tiles 함수

• 입력: 시작 위치, 방문 배열, 타일 종류
• 동작:
  • - 타일이면 오른쪽(dx=1), | 타일이면 아래(dy=1)로만 이동
  • BFS로 같은 종류의 타일이 연속되는지 확인
  • 다른 타일이 나오거나 범위를 벗어나면 1을 반환 (하나의 타일 그룹 완성)

메인 로직

• 모든 위치를 순회하며 방문하지 않은 타일마다 search_tiles 호출
• 각 호출은 연결된 타일 그룹 하나를 카운트

시간 복잡도

• 전체 바닥을 한 번 순회: O(N × M)
• 각 타일은 최대 한 번씩만 방문: O(N × M)
• 전체 시간 복잡도: O(N × M)

N, M ≤ 100이므로 최악의 경우에도 10,000번의 연산으로 충분히 빠르다.

다른 접근 방법

코드의 주석에도 나와있듯이, BFS 대신 단순 반복문으로도 해결 가능하다:

visited = [[False] * M for _ in range(N)]
tile_cnt = 0

for y in range(N):
    for x in range(M):
        if visited[y][x]:
            continue
        
        tile_cnt += 1
        visited[y][x] = True
        
        if floor[y][x] == '-':
            # 오른쪽으로 쭉 방문 처리
            nx = x + 1
            while nx < M and floor[y][nx] == '-':
                visited[y][nx] = True
                nx += 1
        else:
            # 아래로 쭉 방문 처리
            ny = y + 1
            while ny < N and floor[ny][x] == '|':
                visited[ny][x] = True
                ny += 1

print(tile_cnt)

이 방법이 더 간단하고 직관적이지만, 그래프 탐색 연습을 위해 BFS를 사용하는 것도 좋은 방법이다.