[백준_1388] 바닥장식_python

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

 

1388번: 바닥 장식

문제

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

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

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

입력

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

출력

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

 

문제해결

1. 하나는 가로를기준으로, 다른하나는 세로를 기준으로 하여 1씩 증가시켜 'l'혹은 '-'를 확인하는 그리디 방식으로 문제를 해결할 수 있다.

2. '-' 와 'ㅣ' 하나만을 탐색하게끔 깊이우선탐색(DFS)를 활용하여 문제를 해결가능하다.

 

DFS를 더 연습하고 발전시키고 싶어 DFS풀이법으로 포스팅하겠습니다.

 

우선 dfs탐색 알고리즘의 전체적인 틀은 깊이우선 탐색이고 재귀함수를 이용하여 구현가능하다.(bfs는 재귀가 불가능하다)

스택을 활용하기때문에  선입후출의 형태를 띄고있다. dfs의 큰틀은

1.방문처리 

2.현재 노드와 연결된 다른노드들을 재귀적으로 방문

하는 형태로 되어있으며 문제에 따라 방문처리해야 할 스택을 따로 만들거나 하는 변형이 가능하다.

 

해당문제는 세로를 탐색하는dfs1과 가로를 탐색하는 dfs2로 함수를 설정하였고

두 함수가 정상종료되면 True 한번을 반환하게하여 문제에서 요구한 ' 같은 나무 판자'의 조건을 충족시켰습니다.

각 함수에서 반환된 True의 갯수를 출력하면 필요한 나무판자의 개수를 얻을 수 있습니다.

 

코드는 다음과 같습니다.

def dfs1(x,y):#위아래보기
    if x < 0 or x >= n or y < 0 or y >= m:
        return
    if graph[x][y] == '|':
        graph[x][y] = True
        dfs1(x+1,y)
        dfs1(x-1,y)
        return True
    return False

def dfs2(x,y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return
    if graph[x][y] == '-':
        graph[x][y] = True
        dfs2(x,y+1)
        dfs2(x,y-1)
        return True
    return False

n , m = map(int,input().split())
graph = [ list(input()) for _ in range(n) ]
cnt = 0

for i in range(n):
    for j in range(m):
        if dfs1(i,j) == True:
            cnt += 1
        if dfs2(i,j) == True:
            cnt += 1
print(cnt)

 

더 효율적이거나 직관적으로 이해가능한 코드가 있다면 댓글남겨주시면 감사하겠습니다!