백준 3197 백조의호수 파이썬

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

두마리의 백조가 언제 만날 수 있는지 구하는 문제입니다. 간단한 bfs문제인데, 범위가 넓고 시간이 짧아서 플레5로 측정된 문제입니다.
가로, 세로의 길이가 최대 1500이라서 빡빡합니다. 저는 최대 N번의 bfs를 통해서 문제를 해결했습니다.

빙판이 몇일 뒤에 사라지는지 계산

---

빙판은 물과 맞닿아 있는 면이 다음날 녹는 형식으로 사라집니다. 먼저 빙판이 언제 사라지는지를 bfs를 통해서 계산했습니다. 위의 그림과 같은 형식의 빙판이라면 아래와 같은 새로운 board가 생성됩니다.

[0, 0, 0, 1, 2, 3, 3, 2, 1, 0, 0, 1, 1, 0, 1, 2, 2]
[0, 0, 0, 0, 1, 2, 3, 2, 2, 1, 1, 2, 1, 0, 1, 1, 1]
[0, 0, 0, 1, 2, 3, 2, 1, 1, 2, 2, 3, 2, 1, 1, 0, 0]
[0, 0, 1, 2, 3, 2, 1, 0, 0, 1, 2, 3, 3, 2, 1, 0, 0]
[0, 1, 2, 3, 3, 2, 1, 0, 0, 1, 2, 3, 3, 2, 1, 0, 0]
[1, 1, 2, 2, 3, 2, 1, 0, 0, 0, 1, 2, 2, 1, 0, 0, 0]
[0, 0, 1, 1, 2, 2, 1, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 2, 2, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0]

언제 만날 수 있는지 계산

---

두 백조의 위치를 swans리스트에 넣어두고, 첫번째 백조의 위치를 q에 넣습니다. 그리고, 위에서 구한 빙판이 사라지는 날짜중 가장 큰 날짜만큼 반복하며 bfs로 탐색을 합니다. 그러던 중, swans의 2번째 좌표의 값이 L인 순간 탐색을 멈추고 몇일차인지 출력합니다.

첫번째 백조의 좌표부터 사방탐색을 시작해서 
0보다 작은 값을 모두 L로 변경 0보다 큰값을 만날 수 있는 경우
다음 날짜의 q에 삽입
// 0일차 next_q = [[0,2],[1,3],[2,2],[3,0]]
L L L 1 2 3 3 2 1 0 0 1 1 0 1 2 2
L L L L 1 2 3 2 2 1 1 2 1 0 1 1 1
L L L 1 2 3 2 1 1 2 2 3 2 1 1 0 0
L L 1 2 3 2 1 0 0 1 2 3 3 2 1 0 0
L 1 2 3 3 2 1 0 0 1 2 3 3 2 1 0 0
1 1 2 2 3 2 1 0 0 0 1 2 2 1 0 0 0
0 0 1 1 2 2 1 0 0 0 1 2 1 0 0 0 0
0 0 0 0 1 2 2 1 1 0 1 2 1 R 0 0 0

0일차에서 구한 [[0,2],[1,3],[2,2],[3,0]]를 시작q로 설정
1보다 작거나 같은 값으로 이동할 수 있고 모두 L로 변경합니다
// 1일차
L L L L 2 3 3 2 1 0 0 1 1 0 1 2 2
L L L L L 2 3 2 2 1 1 2 1 0 1 1 1
L L L L 2 3 2 1 1 2 2 3 2 1 1 0 0
L L L 2 3 2 1 0 0 1 2 3 3 2 1 0 0
L L 2 3 3 2 1 0 0 1 2 3 3 2 1 0 0
L L 2 2 3 2 1 0 0 0 1 2 2 1 0 0 0
L L L L 2 2 1 0 0 0 1 2 1 0 0 0 0
L L L L L 2 2 1 1 0 1 2 1 R 0 0 0

// 2일차 
L L L L L 3 3 L L L L L L L L L L
L L L L L L 3 L L L L L L L L L L
L L L L L 3 L L L L L 3 L L L L L
L L L L 3 L L L L L L 3 3 L L L L
L L L 3 3 L L L L L L 3 3 L L L L
L L L L 3 L L L L L L L L L L L L
L L L L L L L L L L L L L L L L L
L L L L L L L L L L L L L L L L L

-> R(2번째 백조의 위치) 가 L(첫번째 백조가 갈 수 있는 위치)로 변경되었으므로 
두 백조는 2일이 지나면 만날 수 있다

정답코드

---

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
X, Y = map(int, input().split(' '))
board = []
swans = []
for i in range(X):
  row = list(input())
  board.append(row)

q = deque()
for x in range(X):
  for y in range(Y):
    if board[x][y] == "X":
      board[x][y] = -1
    else:
      if board[x][y] == "L":
        swans.append([x, y])
      board[x][y] = 0
      q.append([x, y])
max_cnt = 0
# 빙판이 몇일 뒤에 사라지는지 계산
while q:
  x, y = q.popleft()
  for i in range(4):
    nx, ny = x+dx[i], y+dy[i]
    if nx < 0 or ny < 0 or nx >= X or ny >= Y:
      continue
    if board[nx][ny] == -1:
      board[nx][ny] = board[x][y]+1
      max_cnt = max(max_cnt, board[nx][ny])
      q.append([nx, ny])

# 두 백조가 언제 만날 수 있는지
# 주변 0탐색 -> 없음 -> 주변 1탐색 -> ...
q = [swans[0]]
for i in range(max_cnt+1):
  next_q = set()
  while q:
    x, y = q.pop()
    for j in range(4):
      nx, ny = x+dx[j], y+dy[j]
      if nx < 0 or ny < 0 or nx >= X or ny >= Y:
        continue
      if board[nx][ny] == "L":
        continue
      if board[nx][ny] <= i:
        board[nx][ny] = "L"
        q.append([nx, ny])
      else:
        next_q.add(x*Y + y)
  x, y = swans[1]
  if board[x][y] == "L":
    print(i)
    break
  for el in list(next_q):
    x = el//Y
    y = el % Y
    q.append([x, y])