12887(경로 게임) - 해결

경로 게임

 

문제

현정이는 경로 게임을 하고 있다.

경로 게임은 정사각형 칸으로 이루어져 있는 직사각형 격자판에서 진행된다. 격자판의 행의 개수는 항상 2이며, 열의 개수는 양수이다. 각 칸은 검정색 또는 하얀색으로 칠해져 있다.

격자에서 왼쪽-오른쪽 경로는 시작 칸이 가장 왼쪽 열에 있는 칸이고, 마지막 칸이 가장 오른쪽 열에 있는 경로이다. 이때, 경로 상의 모든 칸은 하얀색이어야 하며, 경로상에서 연속하는 칸은 모두 인접해야 한다.

격자판의 하얀색 칸을 검정색 칸으로 바꾼 경우에도 왼쪽-오른쪽 경로가 존재할 수도 있다. 이때, 왼쪽-오른족 경로가 존재하면서 바꿀 수 있는 하얀색 칸의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 열의 개수 M이 주어진다. (M ≤ 50)

둘째 줄부터 두 개의 줄에 게임판의 상태가 주어진다. '.'는 하얀색을, '#'는 검정색을 나타낸다.

왼쪽-오른쪽 경로가 항상 존재하는 게임판만 입력으로 주어진다.

 

출력

첫째 줄에 바꿀 수 있는 하얀색 칸의 개수의 최댓값을 출력한다.

---

기본적인 생각은 2행이기 때문에 위와 아래에서 끝까지 거리를 재는 방법을 하려고 하였다.

그리고 총 흰색 길에서 그 길이를 빼면 바꿀 수 있는 흰색 길의 최대값을 구할 수 있다고 생각하였다.

그래서 bfs로 풀기로 하였다.

방향은 뒤로 가는 경우는 없기 때문에 3방향으로 하였다.

그리고 방문행렬은 위와 아래를 따로 구하였고 길이로 하였다.

또한, 처음 시작이 검은 색 길이면 100으로 리턴하였다. 둘다 흰길이면 짧은 거리를 택하여 답을 구하였다.

import sys
input = sys.stdin.readline

N = int(input())

maps = []
maps.append(list(input().strip()))
maps.append(list(input().strip()))

dirs = [(-1,0),(1,0),(0,1)]

# 탐색
def bfs(n):
    # 위아래 2번 방문하기 때문에 초기화
    visit = [[0] * N for _ in range(2)]

    # 검은 색이라면 100으로 리턴
    if maps[n[0]][n[1]] != '.':
        return 100

    # 탐색 시작 visit는 거리
    q = [n]
    visit[n[0]][n[1]] = 1

    while q:
        node = q.pop()
        # 끝에 도착하면 해당 거리 리턴
        if node[1] == N - 1:
            return visit[node[0]][node[1]]

        for dir in dirs:
            nx = node[0] + dir[0]
            ny = node[1] + dir[1]
            # 범위 안이고 방문 안했으며 흰색 길인거
            if 0<= nx < 2 and ny < N and visit[nx][ny] == 0 and maps[nx][ny] == '.':
                # 거리 증가
                visit[nx][ny] = visit[node[0]][node[1]] + 1
                q.append((nx,ny))

# 위와 아래중 거리가 짧은 거
route = min(bfs((0,0)),bfs((1,0)))
# 총 흰 길 중에서 짧은 거리의 흰 길을 빼면 지울 수 있는 길
total = maps[0].count('.') + maps[1].count('.') - route

print(total)