[python]백준 1388번: 바닥 장식(DFS, BFS)

# 1388 바닥 장식
https://www.acmicpc.net/problem/1388

1388번: 바닥 장식

코드

DFS

def dfs_horizontal(x,y):

  # 주어진 범위를 벗어나는 경우에 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
    
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == '-':
  
    # 해당 노드 방문 처리
    graph[x][y] = 'o'
    
    # 좌, 우의 위치들도 모두 재귀적으로 호출
    dfs_horizontal(x, y - 1)
    dfs_horizontal(x, y + 1)

    return True
  return False

def dfs_vertical(x, y):

  # 주어진 범위를 벗어나는 경우에 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == '|':

    graph[x][y] = 'o'

    # 상, 하의 위치들도 모두 재귀적으로 호출
    dfs_vertical(x - 1, y)
    dfs_vertical(x + 1, y)

    return True
  return False

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

# n 세로, m 가로
for i in range(n):
  for j in range(m):
    if graph[i][j] == '-':
      dfs_horizontal(i, j)
      cnt += 1
    elif graph[i][j] == '|':
      dfs_vertical(i, j)
      cnt += 1

print(cnt)

BFS

from collections import deque

def bfs(a, b):
  deq = deque([(a, b)])
  while deq:
    x, y = deq.popleft()
    if graph[x][y] == "-":
      graph[x][y] = 'o'
      if y+1 < m and graph[x][y+1] == "-":
        deq.append((x, y+1)) # 한칸 이동

    elif graph[x][y] == '|':
      graph[x][y] = 'o'
      if x+1 < n and graph[x+1][y] == "|":
        deq.append((x+1, y)) # 한칸 이동

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 graph[i][j] != 'o':
      bfs(i, j)
      cnt += 1

print(cnt)

알고리즘 없이

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

for i in range(n):
  temp = ''
  for j in range(m):
    if graph[i][j] == '-':
      if graph[i][j] != temp:
        cnt += 1
    temp = graph[i][j] #현재위치값을 temp에 저장

for j in range(m):
  temp = ''
  for i in range(n):
    if graph[i][j] == '|':
      if graph[i][j] != temp:
        cnt += 1
    temp = graph[i][j]

print(cnt)

📝 풀이

풀이방법에는 크게 3가지가 있다.
1. DFS 알고리즘을 사용해서 풀기
2. BFS 알고리즘을 사용해서 풀기
3. 알고리즘 없이 풀기
3가지 방식 모두 풀이를 해보고자 한다.

📝 코드 뜯어보기

DFS

def dfs_horizontal(x,y):

  # 주어진 범위를 벗어나는 경우에 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
    
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == '-':
  
    # 해당 노드 방문 처리
    graph[x][y] = 'o'
    
    # 좌, 우의 위치들도 모두 재귀적으로 호출
    dfs_horizontal(x, y - 1)
    dfs_horizontal(x, y + 1)

    return True
  return False

dfs 함수를 만들어준다. 범위설정을 해주는 것이 중요한데, 주어진 n과 m의 범위를 벗어나는 즉시 종료시키고 x와 y값이 음수가 될때에도 종료를 시켜준다.
graph[x][y]가 '-'라면 방문하지 않았다는 뜻이며 꼭 방문처리를 해준다. 방문 처리 후 좌우 위치들도 모두 재귀적으로 호출시켜준다. 모두 방문했다면 dfs를 종료시켜준다.

def dfs_vertical(x, y):

  # 주어진 범위를 벗어나는 경우에 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == '|':

    graph[x][y] = 'o'

    # 상, 하의 위치들도 모두 재귀적으로 호출
    dfs_vertical(x - 1, y)
    dfs_vertical(x + 1, y)

    return True
  return False

세로도 가로와 동일하게 설정해준다.

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

# n 세로, m 가로
for i in range(n):
  for j in range(m):
    if graph[i][j] == '-':
      dfs_horizontal(i, j)
      cnt += 1
    elif graph[i][j] == '|':
      dfs_vertical(i, j)
      cnt += 1

print(cnt)

주어진 n과 m을 저장하고 graph를 생성해준다. 나무 판자의 개수를 출력해야하므로 cnt = 0으로 설정해준다.
이중 반복문을 통해서 모든 범위를 탐색시켜준다. 탐색하면서 '-'이거나 '|'일때 각각의 dfs들을 실행시켜주고 cnt를 카운트 해준다.

BFS

from collections import deque

def bfs(a, b):
  deq = deque([(a, b)])
  while deq:
    x, y = deq.popleft()
    if graph[x][y] == "-":
      graph[x][y] = 'o'
      if y+1 < m and graph[x][y+1] == "-":
        deq.append((x, y+1)) # 한 칸 이동

    elif graph[x][y] == '|':
      graph[x][y] = 'o'
      if x+1 < n and graph[x+1][y] == "|":
        deq.append((x+1, y)) # 한 칸 이동

deque 라이브러리를 불러오고 a, b 값을 deq에 넣어준다. while문을 통해서 deq에 값이 있다면 계속해서 실행시켜준다. deq의 가장 왼쪽값을 빼주면서 x, y에 할당시켜준다.

그래프를 탐색하면서 범위 내에 있으면서 가로(" - ")와 세로(" | ")일 경우에 한 칸씩 이동시켜주면서 방문처리해준다.

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 graph[i][j] != 'o':
      bfs(i, j)
      cnt += 1

동일하게 graph와 cnt를 생성해주고 이중 반복문을 통해 그래프를 탐색시킨다. graph[i][j]가 방문했던 곳이 아니라면 bfs함수를 실행시켜주고 cnt에 카운트해준다.

알고리즘 없이

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

for i in range(n):
  temp = ''
  for j in range(m):
    if graph[i][j] == '-':
      if graph[i][j] != temp:
        cnt += 1
    temp = graph[i][j] #현재위치값을 temp에 저장

n과 m 범위만큼 반복문을 돌고 temp를 통해 임시값을 저장시켜준다.
graph에 현재 값이 ' - '값이면 현재위치의 값을 temp에 저장시켜준다.
추가적으로 ' - '값이 저장된 temp값이랑 다르다면 ' | '값이므로 cnt += 1을 해준다.

for j in range(m):
  temp = ''
  for i in range(n):
    if graph[i][j] == '|':
      if graph[i][j] != temp:
        cnt += 1
    temp = graph[i][j]

print(cnt)

세로도 동일하게 카운트 해주고 최종적으로 cnt를 출력해준다.

참고

https://fre2-dom.tistory.com/103
https://ye5ni.tistory.com/135
https://hiisk.tistory.com/453