백준 3109 - 파이썬

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

3109번: 빵집

문제 풀이

자격증 공부하느라 오랜만에 문제를 풀어봤더니 감을 다 잃은거 같았다. 고민 좀 하다가 감 다시 되찾는다고 생각하고 다른 사람들의 풀이를 찾아봤다.

 

이 문제 풀이의 핵심은 첫번째 열에서 마지막 열에 도달할때 오른쪽, 오른쪽 위, 오른쪽 아래 이렇게 총 3가지의 이동 방향만 있다는 것이다. 알고리즘의 순서는 다음과 같다.

 

1. 방향을 따라 이동하는 문제이기에 BFS, DFS를 떠올려야 한다.

2. 이동 방향의 순서는 오른쪽 위, 오른쪽, 오른쪽 아래일 때 최적의 해를 구할 수 있다. 그래야 다른 파이프를 연결할 가능성도 남겨두고 빵집과 연결할 수 있기 때문이다.(아래 그림 참고)

3. 파이프를 설치한 곳은 다시 방문하지 않는다.

4. 위 과정들을 첫번째 행부터 마지막 행까지 탐색하면 된다.

 

코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
graph = []

for _ in range(n):
  graph.append(list(input().strip()))

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

def pipe(x,y):
  global result
  graph[x][y] = 'o'
  if y == m-1:
    result += 1
    return True
  for i in range(3):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < m:
      if graph[nx][ny] != 'x' and graph[nx][ny] != 'o':
        if pipe(nx,ny):
          return True

result = 0
for i in range(n):
  pipe(i,0)
print(result)

여기서 m-1에 도달할 경우 True를 반환해 줬는데, 이는 첫번째 열에서 행의 위치를 변경하여 마지막 열까지 도달할 수 있는 경우를 말한다. 또한 True를 반환함으로써 파이프를 성공적으로 연결시 재귀함수가 추가적인 연산 없이 빠져나갈 수 있다.왜냐하면 파이프 연결을 성공하였기 때문에 추가적인 탐색을 통해 길을 찾지 않아도 되기 때문이다.

 

느낀 점

이 문제를 백트래킹으로 푸는 방법도 있는거 같은데 이해가 잘 안돼서 다음번에 복습할때 백트래킹으로도 한번 풀어봐야겠다. 실력이 많이 떨어진거 같은데 다시 꾸준히 하면서 실력을 끌어 올려야 되겠다.