Baekjoon-3197-백조의 호수

import sys
from collections import deque
input = sys.stdin.readline

R,C = map(int, input().split())
maps = []
swan = []
for i in range(R):
    line = [c for c in input().strip()]
    maps.append(line)
    for j,c in enumerate(line):
        if c=='L':
            swan.append([i,j])
            maps[i][j] = '.' # change as ocean

# 방법 1: 얼음 없애고 백조 BFS 반복 -> count 하기
visited = [[0]*C for _ in range(R)]
visited_swan = [[0]*C for _ in range(R)]

def remove_ice(queue):
    global visited, maps
    new_queue = deque() # removed ice
    if len(queue)==0:
        # Find all ocean first
        for i in range(R):
            for j in range(C):
                if maps[i][j] == '.' and visited[i][j]==0:
                    queue.append([i,j])
                    visited[i][j] = 1
                    while queue:
                        x,y = queue.popleft()
                        for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
                            if 0<=x+dx<R and 0<=y+dy<C:
                                if visited[x+dx][y+dy]==0:
                                    if maps[x+dx][y+dy]=='.': # ocean BFS
                                        queue.append([x+dx,y+dy])
                                    else: # removed ice queue for next removal
                                        new_queue.append([x+dx,y+dy])
                                    visited[x+dx][y+dy] = 1
    else:
        while queue:
            x,y = queue.popleft()
            for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
                if 0<=x+dx<R and 0<=y+dy<C:
                    if visited[x+dx][y+dy]==0:
                        if maps[x+dx][y+dy]=='X': # removed ice queue for next removal
                            new_queue.append([x+dx,y+dy])
                            visited[x+dx][y+dy] = 1
    for x,y in new_queue:
        maps[x][y] = '.'
    
    return new_queue

def check_swan(queue):
    global visited_swan
    if len(queue) == 0:
        queue = deque([swan[0]])
        visited_swan[swan[0][0]][swan[0][1]] = 1
    new_queue = deque()
    while queue:
        x,y = queue.popleft()
        for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
            if 0<=x+dx<R and 0<=y+dy<C:
                if visited_swan[x+dx][y+dy]==0:
                    if maps[x+dx][y+dy]=='.':
                        queue.append([x+dx,y+dy])
                        visited_swan[x+dx][y+dy] = 1
                        if x+dx==swan[1][0] and y+dy==swan[1][1]:
                            return True, []
                    else:
                        new_queue.append([x+dx,y+dy])
                        visited_swan[x+dx][y+dy] = 1

    return False, new_queue

queue = deque()
swan_queue = deque()
count = 0
result, swan_queue = check_swan(swan_queue)
while not result:
    queue = remove_ice(queue)
    count += 1
    result,swan_queue = check_swan(swan_queue)
print(count)