백준 12887 경로 게임 / python

문제 : 12887

풀이 point

왼쪽 맨끝 칸에서 오른쪽 맨끝 칸으로 가는 경로를 찾는다. 단, 하얀색 칸만 가야한다.

하얀색을 길, 검정색을 벽으로 생각하고 길을 찾는다고 생각하면 된다. 하얀색 칸의 최대값을 구해야하기 때문에 경로는 최소 경로가 되야하고, 경로를 제외한 모든 하얀색 칸은 검정색으로 대체한다고 생각한다.

풀이 방법

경로를 구해야한다. 경로는 왼쪽에서 오른쪽으로 가는 최소 경로를 구하는 것이다. 일단 계속해서 오른쪽으로 간다. 막히면(검정색 만나면) 위 or 아래로 피한뒤 다시 오른쪽으로 간다. 맨 오른쪽으로 가면 끝난다. 그 다음 맨 처음 입력 받은 게임판에 상태에서 흰색을 구한다.

흰색 - 최소 경로

이것이 하얀색 칸의 최댓값이다.

코드

#백준, 12887 경로게임

import sys
input = sys.stdin.readline

MAX = 9999

def bfs(x, y):
    cnt = 1
    if grid[x][y] != '.':
        return MAX
    while y != M-1:
        if grid[x][y+1] == '.':
            y += 1
        else:
            x = 0 if x == 1 else 1
        cnt += 1
    return cnt

M = int(input())
grid = [list(input().rstrip()) for i in range(2)]

white = sum(row.count('.') for row in grid)

print(white-min(bfs(0, 0), bfs(1, 0)))