[Python/코테] 백준 1388 바닥장식

1388 바닥장식

문제 및 조건 설명: https://www.acmicpc.net/problem/1388

알고리즘 설계

💡idea.

1. 같은 타일인지 확인하기 위해 BFS 사용한다.
2. 가로, 세로를 따로 세어 총합을 구한다. - 다른 BFS 함수를 사용한다.

🎲step.

1. 가로(-)일 때는 BFS를 좌, 우에 대해서만 반복 탐색한다.
   1. 전체 그래프를 반복하는데, '-' 일 때만 BFS 시작한다.
2. 세로(|)일 때는 BFS를 상, 하에 대해서만 반복 탐색한다
   1. 전체 그래프를 반복하는데, '|' 일 때만 BFS 시작한다.
3. 두 번 반복한다. BFS 실행을 시작할 때마다 타일의 갯수를 1 증가시킨다.

* 결국 BFS 함수는 반환 값 없이, 과정에서 방문표시를 하기 위해 진행하게 된다.

코드 구현

from collections import deque
import sys

n, m = map(int, input().split())

room = [list(map(str, sys.stdin.readline().strip())) for _ in range(n)]

row_cnt = 0
col_cnt = 0


def bfs_row(x, y):
    room[x][y] = 0

    queue = deque()
    queue.append((x, y))

    # 좌, 우만 확인
    dy = [1, -1]

    while queue:
        x, y = queue.popleft()

        for i in range(2):
            ny = dy[i] + y
            if 0 <= ny < m and room[x][ny] == '-':
                queue.append((x, ny))
                room[x][ny] = 0


def bfs_col(x, y):
    room[x][y] = 0

    queue = deque()
    queue.append((x, y))

    # 상, 하만 확인
    dx = [1, -1]

    while queue:
        x, y = queue.popleft()

        for i in range(2):
            nx = dx[i] + x
            if 0 <= nx < n and room[nx][y] == '|':
                queue.append((nx, y))
                room[nx][y] = 0


for i in range(n):
    for j in range(m):
        if room[i][j] == '-':
            bfs_row(i, j)       # 리턴값이 없어도 됨. 방문 표시가 바뀌니까
            row_cnt += 1


for i in range(n):
    for j in range(m):
        if room[i][j] == '|':
            bfs_col(i, j)
            col_cnt += 1


print(row_cnt+col_cnt)