[파이썬] 백준 1388 : 바닥장식 (실버4)

[파이썬] 백준 1388 : 바닥장식

 

1388번: 바닥 장식

---

문제

---

풀이

 

0. 접근 방식

연결 요소의 개수를 찾는 문제이다. 기존 2차원 배열과 다르게 가로연결, 세로로 연결된 블록들이 하나로 취급되고 가로블록과 세로블록이 나누어져 있어서 별도의 처리가 필요하다.

배열의 크기가 작아서 BFS와 DFS의 차이가 크지 않다. DFS가 더 편하니 DFS로 구현

 

1. 입력 받기 

N,M = map(int,input().split())
arr = []
for i in range(N):
    arr.append(list(input()))
visit = [[False]*M for i in range(N)]

세로 가로 길이를 받아주고 2차원 어레이에 입력을 받는다. 각 개별요소 접근을 위해 문자열을 리스트로 변환해서 추가.

방문을 체크할 visti 어레이를 arr의 형태에 맞게 만든다.

 

2. DFS 함수 작성

def dfs_horizon(x,y):
    if x<0 or y<0 or x>=M or y>=N :
        return 0
    if visit[y][x] == False and arr[y][x]== '-':
        visit[y][x] = True
        arr[y][x] = 0
        return dfs_horizon(x+1,y)
    return 0

def dfs_vertical(x,y):
    if x<0 or y<0 or x>=M or y>=N :
        return 0 
    if visit[y][x] == False and arr[y][x]== '|':
        visit[y][x] = True
        arr[y][x] = 0
        return dfs_vertical(x,y+1)
    return 0

기존의 DFS 문제에서 조건이 추가되어서 가로블록을 탐색하는 DFS, 세로 블록을 탐색하는 DFS 함수를 따로 구현하였다.

가로 혹은 세로 블록에서 연결된 요소들을 탐색할 때 하나만 찾으면 우,하 방향으로 모두 탐색할 수 있다.

나머지는 기존의 DFS 문제와 똑같이 방문하지 않았을 경우 방문 처리를 해주고 재탐색하지 않도록 arr을 0으로 바꿔준다.

 

3. 결과 출력

count = 0
for i in range(N):
    for j in range(M):
        if arr[i][j] == '-':
            count += 1
            dfs_horizon(j,i)
        elif arr[i][j] == '|':
            count += 1
            dfs_vertical(j,i)
print(count)

DFS 함수를 실행할 수 있을 때 마다 함수를 호출해주고 count를 늘리면 된다.

 

---

전체 코드

N,M = map(int,input().split())
arr = []
for i in range(N):
    arr.append(list(input()))
visit = [[False]*M for i in range(N)]

def dfs_horizon(x,y):
    if x<0 or y<0 or x>=M or y>=N :
        return 0
    if visit[y][x] == False and arr[y][x]== '-':
        visit[y][x] = True
        arr[y][x] = 0
        return dfs_horizon(x+1,y)
    return 0

def dfs_vertical(x,y):
    if x<0 or y<0 or x>=M or y>=N :
        return 0 
    if visit[y][x] == False and arr[y][x]== '|':
        visit[y][x] = True
        arr[y][x] = 0
        return dfs_vertical(x,y+1)
    return 0

count = 0
for i in range(N):
    for j in range(M):
        if arr[i][j] == '-':
            count += 1
            dfs_horizon(j,i)
        elif arr[i][j] == '|':
            count += 1
            dfs_vertical(j,i)
print(count)