[python] 백준 3109 빵집

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

3109번: 빵집

 

문제 해결

• 우선 0열 전체가 근처 빵집 가스관이고 c-1열 전체가 원웅이 빵집 가스관이다.
• 한번에 1열씩 이동한다. 행으로는 -1,0,1행 움직일 수 있다.
• 0행부터 r-1행까지 조사한다고 할 때 겹치지 않는 최대한 많은 파이프를 만들려면 -1행으로 움직이는 길을 만들수록 좋다. 차선책이 0행이고 악의수는 밑으로 1행 움직이는 것이다.
• 파이프 하나 완성시킬 때마다 +1 씩 정답이 증가한다.
• 파이프를 연결하는 과정은 dfs가 편하다. 계속 이어서 만드는 것이고 만든 지역은 표시를 해놔야 한다.(visited)

 

CODE

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = [list(str(input().rstrip())) for _ in range(r)]
visited = [[False for _ in range(c)] for _ in range(r)]

def dfs(x,y):
    if y==c-1:
        return True
    for dx in [-1,0,1]:
        new_x = x + dx
        new_y = y + 1
        if 0<= new_x <= r-1 and 0<= new_y <= c-1:
            if board[new_x][new_y] != "x" and visited[new_x][new_y] == False:
                visited[new_x][new_y] = True
                if dfs(new_x, new_y):
                    return True
    return False

ans = 0
for i in range(r):
    if dfs(i,0):
        ans += 1
print(ans)