[python] 백준 - 3109(빵집)

골드2 문제이며, 제한 시간은 1초이다.

문제

해결 과정

우선 깊이 우선 탐색을 통해서 맨 끝 열까지 갈 수 있는지 판단하는 것이 좋아보였다. 그래서 dfs를 수행하며 이미 방문한 곳은 'x'로 바꿔주며 진행한다. 맨 끝 열에 도착했다면 True를 반환하고, 그렇지 않은 경우에는 False를 반환한다. dfs를 수행할 때 반드시 오른쪽 상단, 중단, 하단 순으로 탐색한다.

해결 과정에 대한 근거

1. dfs를 수행할 때 반드시 오른쪽 상단, 중단, 하단 순으로 탐색하는 이유는 더 많은 파이프라인을 설치하기 위해 공간을 확보하기 위함이다.
2. 이미 탐색을 진행한 경로가 맨 끝 열에 도착하지 못한다는 사실을 한 번 알게되면 더 이상 그 경로는 탐색할 필요가 없다는 것을 알 수 있다. 따라서 방문한 곳은 맨 끝 열에 도착하든 안하든 'x'로 바꿔주는 것이다.

import sys
sys.setrecursionlimit(10000)

def dfs(x, y):
  if y == m - 1:
    return True

  for i in range(3):
    nx = x + dx[i]
    ny = y + 1
    if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == '.':
      graph[nx][ny] = 'x'
      if dfs(nx, ny):
        return True
  return False

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

dx = [-1, 0, 1]
answer = 0

for x in range(n):
  if dfs(x, 0):
    answer += 1

print(answer)

이 문제는 그리디적인 요소가 있어서 그리디 유형으로 분류도 되어있다. 위에서도 언급했지만, 현재 상황에서 반드시 오른쪽 상단, 중단, 하단 순으로 탐색하는 것이 그리디적인 요소이다.