[파이썬] 백준 3109 : 빵집 (골드2)

[파이썬] 백준 3109: 빵집 (골드2)

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

---

풀이

방향성 생각

• 왼쪽 위에서 탐색을 시작한다고 하면, 파이프를 최대한 오른쪽 아래에서 멀어지게 설치해야함.
  • 파이프를 겹쳐서 놓을 수 없기 때문에, 다른 파이프를 막을 수 있기 때문
• 위쪽에서 탐색을 시작해서 최대한 파이프를 위에다 갖다놓자.
• 탐색 도중에 끝까지 도달하지 못하면, 다른 경로를 통해서 그 지점에 도달했을 경우에도 도달하지 못한다.
• 탐색하면서 arr를 바꿔준다. 백트래킹처럼 원상태로 돌릴 필요는 없다.

 

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

H,W = map(int,input().split())
arr = [list(input()) for _ in range(H)]

inside = lambda x,y : 0<=x<W and 0<=y<H

answer = 0
def dfs(x,y):

    global answer

    if x == W-1:
        arr[y][x] = answer
        answer += 1
        return True

    arr[y][x] = answer
    for ny in (y-1,y,y+1):
        if inside(x+1,ny) and arr[ny][x+1] == '.' and dfs(x+1,ny):
            return True
    return False

for y in range(H):
    if arr[y][0] == '.':
        dfs(0,y)

print(answer)

코멘트

• .