[Python] 12887번 경로 게임

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

12887번: 경로 게임

---

 

24/03/20

 

 

BFS응용 혹은 그리디로 풀 수 있는 간단한 문제이다.

---

 

문제 접근 방식:

 

 

접근 방식은 굉장히 간단하다.

 

왼쪽-오른쪽 경로 중 최단 거리의 경로를 찾고, 그 경로를 제외하고 다 색칠하면 최대한 많은 하얀색 칸을 칠할 수 있을 것이라는 아이디어이다.

 

따라서, 현재 흰색 칸이 몇 개 있는지 구하고, BFS를 통해 최단 거리를 구한 뒤, 흰색 칸에서 최단 거리만큼을 빼주었다.

 

최단 거리 상의 경로는 항상 흰색 칸 일 것이며, 이를 제외한 흰색 칸을 모두 칠해야 하기 때문이다.

 

이를 그대로 구현하면 된다.

 

혹은, 판의 모양이 $2 \times N$칸 있다는 점을 이용하여, 벽에 막히는 순간 위나 아래로 움직인 뒤, 다음 벽으로 갈 때까지 계속 오른쪽 움직이는, 그리디한 접근 방식으로 풀어도 무방하다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 12887번 경로 게임
# BFS
'''
접근 방법:
왼쪽-오른쪽 경로 중 최단 거리 경로를 찾아보자.
그 경로 제외하고 다 색칠하면 최대한 많은 하얀색 칸을 칠할 수 있지 않을까?
'''
import sys
input = sys.stdin.readline
from collections import deque

dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
M = int(input())  # 열의 개수
graph = [list(input().rstrip()) for _ in range(2)]
white = 0
for i in range(2):
    for j in range(M):
        if graph[i][j] == '.':
            white += 1
black = 2*M - white
queue = deque()
if graph[0][0] == '.':
    queue.append((0, 0, 1))
    graph[0][0] = '#'
if graph[1][0] == '.':
    queue.append((1, 0, 1))
    graph[1][0] = '#'
min_dist = 0
while queue:
    r, c, dist = queue.popleft()
    if c == M-1:
        min_dist = dist
        break
    for i in range(4):
        nr, nc = r+dr[i], c+dc[i]
        if 0 <= nr < 2 and 0 <= nc < M and graph[nr][nc] == '.':
            graph[nr][nc] = '#'
            queue.append((nr, nc, dist+1))
print(white - min_dist)