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

문제

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

1388번: 바닥 장식

 

 

🐍파이썬

import sys
sys.setrecursionlimit(10**6)
n, m = map(int, sys.stdin.readline().split())
bang = []
for _ in range(n):
    bang.append(list(sys.stdin.readline().rstrip()))

def dfs1(y, x):	#y, x 순서 주의
    if x >= m or y >= n or x < 0 or y < 0:	#범위를 벗어나면 return
        return
    if bang[y][x] == "-":
        bang[y][x] = "o"	#방문처리
        for i in [-1, 1]:	#좌우로 움직이기
            nx = x + i
            dfs1(y, nx)	#y, x 순서 주의
def dfs2(y, x):
    if x >= m or y >= n or x < 0 or y < 0:
        return
    if bang[y][x] == "|":
        bang[y][x] = "o"
        for i in [-1, 1]:	#상하로 움직이기
            ny = y + i
            dfs2(ny, x)
cnt = 0
for i in range(n):  #세로(y)
    for j in range(m):  #가로(x)
        if bang[i][j] == "-":	#"-"인 경우 
            dfs1(i, j)	#dfs1수행 -> "-"를 찾을 수 없을 때까지 탐색
            cnt += 1	#dfs1수행한 횟수 체크
        elif bang[i][j] == "|":
            dfs2(i, j)
            cnt += 1
print(cnt)

dfs1, dfs2 나누지 않고 dfs함수 하나만 만든 뒤 그 안에서 분기로 해결하려 했는데 실패하고 결국 함수를 두 개 만들었다. 

인덱스 x, y 처리하는 데도 시간이 많이 걸렸다. 이차원 배열 문제 풀 때는 조금 더 배열의 범위를 신경쓰면서 신중히 접근해야겠다.

 

 

다른 풀이 방법

DFS 다른 방식의 풀이

import sys
input = sys.stdin.readline
def dfs(x,y):
    visited[x][y] = True
    if y+1 < M and graph[x][y] == '-' and graph[x][y+1] == '-':     # `-`이고 다음이 `-`일 경우 재귀
        dfs(x,y+1)
    elif x+1 < N and graph[x][y] == '|' and graph[x+1][y] == '|':   # `|`이고 다음이 `|`일 경우 재귀
        dfs(x+1,y)

N, M = map(int,input().split())
graph = [input() for i in range(N)]
visited = [[False]*M for i in range(N)]
total = 0

for i in range(N):
    for j in range(M):
        if visited[i][j] == False:
            dfs(i,j)
            total += 1
print(total)

---

n, m = map(int, input().split())
floor = []
for _ in range(n):
    w = input()
    w = list(w)
    floor.append(w)
cnt = 0
for i in range(n):
    if floor[i][0] == '-':
        cnt += 1
    for j in range(1, m):
        if floor[i][j] == '-' and floor[i][j-1] == "|":
            cnt += 1

for i in range(m):
    if floor[0][i] == '|':
        cnt += 1
    for j in range(1, n):
        if floor[j][i] == '|' and floor[j-1][i] == "-":
            cnt += 1
print(cnt)