[백준 17267번] 상남자 (Python3)

import sys
input = sys.stdin.readline
from collections import *
dy = [0,0,-1,1]; dx = [-1,1,0,0]

def BFS(n,d):
  visited = [[0]*M for i in range(N)]
  dq = deque([(sy,sx,0)])
  while dq:
    y,x,cnt = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0 and not visited[y1][x1]|board[y1][x1]:
        if i==d:
          if cnt < n:
            dq.append((y1,x1,cnt+1))
        else:
          dq.appendleft((y1,x1,cnt))
  return visited
      
N,M = map(int,input().split())
L,R = map(int,input().split())

board = [[*map(int,input().strip())] for i in range(N)]

for i in range(N):
  for j in range(M):
    if board[i][j]==2:
      sy,sx = i,j; board[i][j] = 0

visitedL = BFS(L,0); visitedR = BFS(R,1)
print(sum([visitedL[i][j]&visitedR[i][j] for i in range(N) for j in range(M)]))

0-1 BFS를 이용하여 해결하였다.

 

풀이를 요약하면,

1. 좌 방향으로 L번 이동하여 도달할 수 있는 땅을 구한다. 이때 위,아래,우 방향에 대해서는 appendleft를 한다.

2. 우 방향으로 R번 이동하여 도달할 수 있는 땅을 구한다. 이때 위,아래,좌 방향에 대해서는 appendleft를 한다.

3. 1,2에서 도달한 땅에 대해서 두번 모두 도달할 수 있는 땅의 개수를 출력한다.

 

전구를 켜라 [백준 2423번] 전구를 켜라 (Python3) (tistory.com) 문제에서 처음 접한 0-1 BFS는 다양한 문제에서 활용할 수 있는 것 같다.

 

 

오늘의 교훈) 0-1 BFS는 유용하다.