[백준] 바닥 장식(python)

백준, 바닥 장식

1388번: 바닥 장식

TL;DR

• 그래프 탐색
• 깊이 우선 탐색(DFS)

문제 요약

1. 바닥 장식을 위해서 필요한 나무 판자의 개수를 구하는 프로그램이다.
2. -가 같은 행에 위치한다면 하나의 나무 판자로 만들 수 있다.
3. |가 같은 열에 위치한다면 하나의 나무 판자로 만들 수 있다.

 

- 섬의 개수 문제의 응용 버전이다. -일 때는 인접한 행에 동일한 것이 있는지 확인하면 되고 |일 때는 인접한 열에 동일한 것이 있는지 확인하면 된다.

입출력 형태

입출력 예시

 

예시 3 :: 같은 행이 7개, 같은 열이 6개이기 때문에 총 13개가 답이 된다.

풀이

깊이 우선 탐색(DFS)를 사용하면 문제를 해결할 수 있다.

import sys
INPUT = sys.stdin.readline

N, M = map(int, INPUT().split())
graph = []
for _ in range(N):
  graph.append(list(INPUT()[:-1]))
answer = 0

def dfs(x, y):
  if graph[x][y] == '|':
    graph[x][y] = 'o'

    for _x in [1, -1]:
      X = x + _x
      if (X > 0 and X < N) and graph[X][y] == '|':
        dfs(X, y)

  if graph[x][y] == '-':
    graph[x][y] = 'o'

    for _y in [1, -1]:
      Y = y + _y
      if (Y > 0 and Y < M) and graph[x][Y] == '-':
        dfs(x, Y)

for i in range(N):
  for j in range(M):
    if graph[i][j] == '|' or graph[i][j] == '-':
      dfs(i, j)
      answer += 1
print(answer)

 

방문한 노드의 값이 -라면 양 옆(문제에서는 y좌표를 -1, 1)을 확인하고 동일하다면 dfs를 수행한다.

방문한 노드의 값이 |라면 위 아래(문제에서의 x좌표를 -1, 1)을 확인하고 동일하다면 dfs를 수행한다.

dfs를 수행하고 나면 인접한 값들은 모두 o로 변경되어 더 이상 조회하지 않는다. 각 수행이 끝나면 동일한 행 또는 열에 위치한 연속된 바닥 장식을 확인할 수 있기 때문에 수행한 dfs의 순서를 세면 원하는 답을 얻을 수 있다.

- 한 번의 dfs 수행 당 하나의 나무 판자를 사용하는 것이다.

다른 풀이

DFS와 같은 방법이 아닌 입력 받은 평면을 조회하며 원하는 조건을 마주했을 때 숫자를 계산하는 방법으로도 계산할 수 있다. 문제를 푼 후 다른 맞은 사람의 풀이를 확인해보도록 하자.