바닥 장식(백준 1338번)

바닥 장식

1388번: 바닥 장식

1388번: 바닥 장식

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

 

다음과 같이 입력이 주어진다면 4개의 길이 판자가 4개가 있음으로 4를 출력해준다.

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

다음 예시는 13을 출력해주면 된다.

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

문제 해결

내가 접근한 방법의 경우 2중 for 루프를 돌면서 입력값 하나 하나 들어가서 bfs를 해준다. bfs를 완료하고 나면 방문한 정점들은 visited 체크 돼있음으로 다시 방문하지 않는다.

for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            visited[i][j] = True
            bfs(i, j)

만약 i, j의 값이 ‘-’ 일경우 열 방향으로 인접한 정점만을 탐색하면서 카운트를 올린다. 만약 ‘|’ 라면 행 방향으로 인접한 정점을 탐색 하면서 카운트를 올린다.

 

‘-’로 탐색을 시작했다면 ‘|’를 만나면 탐색이 종료되고, ‘|’ 로 시작했다면 ‘-’를 만나면 길이를 반환하고 탐색을 종료한다.

 

그리고 열, 행 방향으로만 탐색하기 위해서 방향 벡터를 1, -1 로만 두 요소만 주었다.

 

코드

# 바닥 장식
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = []
dx = [1,-1]
dy = [1,-1]
visited = [[False for _ in range(m)] for _ in range(n)]
q = deque()

for i in range(n):
    graph.append(list(sys.stdin.readline().rstrip()))
cnt = 0

def bfs(x, y):
    global cnt
    tree = graph[x][y]
    q.append((x,y))
    if tree == '-':
        while q:
            cx, cy = q.popleft()
            for dir in range(2):
                # 열 방향으로만 탐색
                nx = cx
                ny = dy[dir] + cy
                if 0 <= nx < n and  0 <= ny < m:
                    if graph[nx][ny] == '|':
                        break
                    if not visited[nx][ny]:
                        visited[nx][ny] = True
                        q.append((nx,ny))
        cnt += 1
        
    elif tree == '|':
        while q:
            cx, cy = q.popleft()
            for dir in range(2):
                # 행 방향으로만 탐색
                nx = dx[dir] + cx
                ny = cy
                if 0 <= nx < n and  0 <= ny < m:
                    if graph[nx][ny] == '-':
                        break
                    if not visited[nx][ny]:
                        visited[nx][ny] = True
                        q.append((nx,ny))
        cnt += 1        
       
for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            visited[i][j] = True
            bfs(i, j)

print(cnt)