BFS

숨바꼭질 실1

from collections import deque
N, K = map(int, input().split())
visited = [0]*100001

def bfs(cur):
  global visited
  if cur == K :
    return visited[cur]
  
  queue = deque()
  queue.append(cur)

  while queue:
    now = queue.popleft()

    for nxt in [now+1, now-1, now*2]:
      if 0 <= nxt <= 100000 and visited[nxt] == 0:
        visited[nxt] = visited[now] + 1
        queue.append(nxt)


bfs(N)
print(visited[K])

미로찾기 실1

• BFS는 "가까운 곳부터 차례대로" 탐색하기 때문에 목적지에 도착하는 순간이 곧 가장 빠른 길이다

from collections import deque
N, M = map(int, input().split())
data = [list(map(int, input())) for _ in range(N)]


dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(start_x, start_y):
  queue = deque([(start_x, start_y)])
  visited = [[-1]*M for _ in range(N)]
  visited[start_x][start_y] = 1

  while queue:
    x, y = queue.popleft()

    
    for k in range(4):
      nx, ny = x+dx[k], y + dy[k]
      if 0<=nx<N and 0<=ny<M and visited[nx][ny] == -1 and data[nx][ny] == 1:
        visited[nx][ny] = visited[x][y] + 1
        queue.append((nx, ny))
  
  print(visited[N-1][M-1])


bfs(0,0)

그림 실1

from collections import deque
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
visited = [[-1]*m for _ in range(n)]
max_ans = 0
pic = 0
def bfs(start_x, start_y):
  global visited
  queue = deque([(start_x, start_y)])
  global max_ans
  ans = 1

  while queue:
    x, y = queue.popleft()
    visited[x][y] = 1
    
    
    for k in range(4):
      nx, ny = x + dx[k], y + dy[k]
      if 0<=nx<n and 0<=ny<m and visited[nx][ny] == -1 and data[nx][ny] == 1:
        queue.append((nx, ny))
        visited[nx][ny] = 1
        ans += 1
  max_ans = max(ans, max_ans)
  return max_ans

for i in range(n):
  for j in range(m):
    if data[i][j] == 1 and visited[i][j] == -1:
      result = bfs(i,j)
      pic += 1
print(pic)
print(max_ans)