문제

예시 입력 1

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

예시 출력 1

4

예시 입력 2

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

예시 출력 2

31

예시 입력 3

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

예시 출력 3

13

문제 이해

일단 이 문제가 왜 실버4인지 모르겠다. 지금까지 DFS문제를 풀었지만, 간단한 DFS 문제도 실버2 등급이었는데, 이건 좀 더 응용해서 풀게하는 문제인데 실버4다. 모든 문제가 정확한 등급을 받기는 어려운 것 같다. 어떻게 보면 이 문제가 저평가된게 아니라 다른 DFS문제가 고평가 되어서 등급을 받은게 아닐까.

DFS/BFS의 응용문제이다. type을 두가지로 나누어서 DFS를 돌린다. DFS 함수를 만들때 매개변수를 y, x 좌표값과 감지하는 type을 넣어준다.

type이 "-"라면 x값을 1증가시킨 값이 범위안에 속하고, 같은 타입인지 비교한 후 맞다면 DFS재호출을 실시한다.

type이 "|"라면 y값을 1증가시킨 값이 범위안에 속하고, 같은 타입이면 재호출한다.

둘 다 DFS호출시 값을 기존 값과 다른 값인 0으로 바꾸어주고, 메인에서 DFS를 호출했을때 cnt값을 늘려준다. 메인에서 한번 호출하면 그게 한 판자이기 때문이다.

type을 나눠서 DFS를 만드는 건 처음이라서 낯설면서 재미있었다.

코드

# 백준 1388번 바닥 장식

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def DFS(y, x, type):
    global floor_map
    # visited 없이 맵에 방문처리
    floor_map[y][x] = 0

    if type == "-":
        
        if 0 <= (x+1) < M and floor_map[y][x+1] == type:
            DFS(y, x+1, type)
    elif type == "|":

        if 0 <= (y+1) < N and floor_map[y+1][x] == type:
            DFS(y+1, x, type)

# 0. 입력 및 초기화
N, M = map(int, input().split()) #N세로 M가로
floor_map = []
cnt = 0

# 1. 연결 정보 입력
for i in range(N):
    # 다 붙여서 입력을 받을때는 rstrip으로 오른쪽 공백을 빼고 받아야함
    floor_map.append(list(input().rstrip()))

# 2. DFS호출

for i in range(N):
    for j in range(M):
        if floor_map[i][j] == "-":
            DFS(i, j, "-")
            cnt += 1
        elif floor_map[i][j] == "|":
            DFS(i, j, "|")
            cnt += 1

# 3. 출력
print(cnt)