[백준] 1388번: 바닥 장식 (python)

1388번: 바닥 장식

---

문제 )

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

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

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

 

 

입력 :

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

 

출력 :

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

 

 

 

 

풀이)

처음 이 문제를 보았을 땐, 분류를 알고 들어가서 인지 BFS로 접근해야 된다는 생각이 있었고.

0,0 에서 시작하여 n,m에 도달할 때까지 이전 판자와 다음 판자가 다르면 cnt에 1을 더하는 방향으로 하려고 했다.

하지만 이러한 방식의 경우 판자 전체를 도는 것은 맞지만 불규칙적으로 리스트를 순회하므로 올바른 답을 도출해내지 못했다.

 

따라서 다른 방법을 모색했는데,

행에는 " - ", 열에서는 " | " 을 유지해야 하므로, 행과 열을 따로 체크하면서 올바른 판자인지 확인하고, 이전 판자와 다르면 카운트를 늘리는 방향으로 문제를 풀어보았다. 

 

정답이 나오기는 했으나.. 이게 깊이 우선 탐색이나 너비 우선 탐색와 어떠한 식으로 연관되어 있는지는 잘 모르겠다.

 

행에서 | 이 나올 경우 cnt +1, 열에서 - 가 나올경우 cnt +1
n, m = map(int, input().split())
g = [list(input()) for i in range(n)]
 
cnt = 0
for i in range(n):
    pre = "/"
    for j in range(m):
        if g[i][j] == "-":
            if g[i][j] != pre:
                cnt += 1
        pre = g[i][j]
 
for i in range(m):
    pre = "/"
    for j in range(n):
        if g[j][i] == "|":
            if g[j][i] != pre:
                cnt += 1
        pre = g[j][i]
 
print(cnt)

 

 

 

---

출처 : https://www.acmicpc.net/problem/1388

1388번: 바닥 장식