[Python/파이썬] 백준 28228번 Parking Party

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

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parking_lot = [list(input()) for _ in range(n)]

# 위쪽
for c in range(m):
    r = 0
    while r < n and parking_lot[r][c] != "o":
        parking_lot[r][c] = "-"
        r += 1
# 아래쪽
for c in range(m):
    r = n-1
    while r >= 0 and parking_lot[r][c] != "o":
        parking_lot[r][c] = "-"
        r -= 1
# 왼쪽
for r in range(n):
    c = 0
    while c < m and parking_lot[r][c] != "o":
        parking_lot[r][c] = "-"
        c += 1
# 오른쪽
for r in range(n):
    c = m-1
    while c >= 0 and parking_lot[r][c] != "o":
        parking_lot[r][c] = "-"
        c -= 1

answer = 0
for i in range(n):
    for j in range(m):
        if parking_lot[i][j] == "-":
            answer += 1
print(answer)

 

처음에는 BFS를 이용하여 바깥 테두리와 인접해있는 칸들과 연결된 빈 칸의 개수를 찾는 문제인줄 알았는데, 아니었다. 문제를 다시 보니 차들은 입장한 방향 그대로 앞으로 직진만 가능하다. 그렇기 때문에 4방향 모두 움직일 수 있다고 가정하는 BFS로 풀면 틀린다.

 

다시 단순하게 생각해보니 그냥 주차장의 테두리에 해당하는 모든 칸에서 행에 평행하게 또는 열에 평행하게 직진하여 벽에 닿거나 주차장의 끝에 도달하기 전까지 모두 차를 채울 수 있다고 생각하면 되는 문제였다.

 

그래서 테두리 4면에서 주차장의 끝에 닿거나 벽에 닿을 때까지 직진하며 지나가는 칸들을 "-"으로 표시해두고, 모든 테두리를 다 돌아본 뒤에 전체 주차장에서 "-"의 개수를 세면 답이다.