[DFS 알고리즘] 1388번 바닥장식 풀이(파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 백준에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다.

그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다.

 

[접근 방식]

- 문제에서 요구하는 역량은 무엇인지?

- 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다.

 

- 백준 문제 링크입니다. : https://www.acmicpc.net/problem/1388

1388번: 바닥 장식

아래 작성된 답안은 제가 직접 작성 후 백준 페이지에서 채점하여 정답으로 인정된 답안입니다.
공식 답안이 아니므로 최적의 해가 아닐 수 있으며, 답안은 다른 분들과 상이할 수 있습니다.

 

[풀이]

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

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

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

for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            count += 1
        if long(i,j) == True:
            count += 1
print(count)

이 문제는 가로 작대기(-) 와 세로 작대기(|)를 각각 구분하는 함수를 구성하여 해결했습니다.

1. 가로 작대기 개수 확인(dfs함수)

dfs 함수의 경우,

입력된 전체 바닥 범위(n x m) 를 벗어난 x,y값은 제외.

오직 행 별로 인접한 '-' 표시를 1로 변경하여 방문 표시를 남기고, 좌우에 인접한 '-' 표시가 있는지 확인하여 있으면 재귀함수로 호출.

좌우에 인접한 '-' 표시가 없는 경우 최종적으로 True를 출력.

 

2. 세로 작대기 개수 확인(long함수)

long 함수의 경우,(dfs 함수와 기본 로직은 동일)

입력된 전체 바닥 범위(n x m) 를 벗어난 x,y값은 제외.

오직 행 별로 인접한 '|' 표시를 1로 변경하여 방문 표시를 남기고, 상하에 인접한 '|' 표시가 있는지 확인하여 있으면 재귀함수로 호출.

좌우에 인접한 '|' 표시가 없는 경우 최종적으로 True를 출력.

 

3. 2중 for문으로 바닥 범위 내 모든 좌표를 하나씩 조사하여 True 값이 총 몇번 나왔는지 확인

 

감사합니다.