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

바닥 장식

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

1388번: 바닥 장식

 

문제

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

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

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

 

입력

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

 

출력

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

 

테스트케이스

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

-> 4

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

-> 31

 

풀이

이것이 취업을 위한 코딩테스트다 - DFS & BFS: 실전 문제 1 음료수 얼려 먹기 문제를 응용해서 풀었다.

 

기본적인 아이디어는 DFS를 이용한 완전 탐색이다. 매 노드에 대해 DFS를 수행하되 이전에 방문하지 않은 원소의 수만을 세고, 해당 노드를 방문하면서 재귀적으로 인접한 노드에 대해 DFS를 수행한다.

이때 ‘-’라면 좌우로만 탐색하고(y +- 1), ‘|’라면 상하로만 탐색한다(x +- 1). 

재귀적으로 탐색하는 과정에서 하나로 연결된 나무 판자는 모두 방문 처리 (floor[x][y] = 0) 하므로, 다음에 for문에서 해당 원소를 탐색했을 때 cnt가 증가하지 않는다. 이때 방문 처리는 ‘-’과 ‘|’이 아닌 값이라면 어떤 값으로 해도 무관하다.

 

이전에 검사하던 방향(상하 또는 좌우)과 동일한 방향으로만 검사해야 하므로 직전에 방문한 원소가 ‘-’인지 ‘|’인지 확인하기 위해 dfs()에 last라는 파라미터를 넣었다. for문에서 dfs를 호출할 때에는 현재 방문하는 원소의 방향으로 움직이기 위해 floor[i][j]를 넣었다.

 

시행착오 및 배운 점 

1. 처음에는 좌우/상하 모두 탐색했는데, 생각해보니 for문으로 순회할 때 좌->우, 상->하 방향으로 탐색하므로 오른쪽/아래쪽에 있는 원소만 탐색하면 됐다. 그래서 좌/상단 탐색 dfs 재귀 코드 두 줄을 지웠고, 실행 시간이 4ms 단축되었다. 

 

2. 문제를 풀면서 내가 이 n*m 2차원 배열을 무척 헷갈려한다는 사실을 깨달았다. 재귀 호출에 사용하는 x, y는 좌표계가 아니고 인덱스임을 명심하자.

• n*m일 때 floor[0][0] ~ floor[n-1][m-1] 이므로 for 루프는 n 안에 m이 있어야 한다.
• 배열 범위 안에 있는지 검사할 때도 x는 0~n-1, y는 0~m-1인지 확인해야 한다.

def dfs(x, y, last):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
...
for i in range(n):
    for j in range(m):
        if dfs(i, j, floor[i][j]):
            cnt += 1

 

최종 코드

# 바닥 장식: DFS
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
floor = []
for i in range(n):
    floor.append(list(input().rstrip()))
def dfs(x, y, last):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    if floor[x][y] == '-' and last == '-':
        floor[x][y] = 0
        dfs(x, y+1, '-')
        return True
    elif floor[x][y] == '|' and last == '|':
        floor[x][y] = 0
        dfs(x+1, y, '|')
        return True
    return False
cnt = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j, floor[i][j]):
            cnt += 1
print(cnt)

메모리: 31256 KB / 시간: 44 ms